Submission #3274645
Source Code Expand
#include <bits/stdc++.h> using namespace std; using LL = long long int; #define int long long #define INF 1145141919 #define INF_LL 114514191981036436 const int MAX_N = 4005; const int MAX_T = 4005; template< class T > struct ConvexHullTrickAddQueryMonotone { deque< pair< T, T > > L; int isdec; ConvexHullTrickAddQueryMonotone() : isdec(-1) {} inline T getX(const pair< T, T > &a, const T &x) { return (a.first * x + a.second); } inline bool check(const pair< T, T > &a, const pair< T, T > &b, const pair< T, T > &c) { return ((b.first - a.first) * (c.second - b.second) >= (b.second - a.second) * (c.first - b.first)); } inline bool empty() { return (L.empty()); } void add(T a, T b) { pair< T, T > line(a, b); if(!L.empty() && L.back().first == a) { line.second = min(line.second, L.back().second); L.pop_back(); } while(L.size() >= 2 && check(L[L.size() - 2], L.back(), line)) L.pop_back(); L.emplace_back(line); } T getMinimumQuery(T x) { int low = -1, high = (int) L.size() - 1; while(high - low > 1) { int mid = (low + high) >> 1; if((getX(L[mid], x) >= getX(L[mid + 1], x))) low = mid; else high = mid; } return (getX(L[high], x)); } T getMinimumQueryMonotone(T x) { while(L.size() >= 2 && getX(L[0], x) >= getX(L[1], x)) { L.pop_front(); } return (getX(L[0], x)); } }; int N; int T; class Song{ public: int t, p, f; bool operator < (const Song& song) const { return f < song.f; } }songList[MAX_N]; int dp[MAX_N][MAX_T]; signed main() { cin >> N >> T; for(int i = 0; i < N; i++) { cin >> songList[i].t >> songList[i].p >> songList[i].f; } sort(songList, songList+N); vector<ConvexHullTrickAddQueryMonotone<int> > cht; for(int i = 0; i <= T+1; i++) { cht.push_back(ConvexHullTrickAddQueryMonotone<int>()); } for(int i = 1; i <= N; i++) { for(int t = 0; t <= T; t++) { dp[i][t] = -INF_LL; } } int ans = -INF_LL; for(int i = 1; i <= N; i++) { const Song& song = songList[i-1]; for(int t = T; song.t <= t; t--) { if(t == song.t) { dp[i][t] = max(dp[i][t], song.p); } else { if(cht[t-song.t].empty()) { continue; } dp[i][t] = max(dp[i][t], song.p - song.f * song.f - cht[t-song.t].getMinimumQueryMonotone(song.f)); } } for(int t = T; t >= 0; t--) { if(dp[i][t] == -INF_LL) continue; cht[t].add(-2*song.f, -(dp[i][t] - song.f * song.f)); } } for(int i = 0; i <= N; i++) { for(int j = 0; j <= T; j++) { ans = max(ans, dp[i][j]); } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | I - Live Programming |
User | takoshi |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 3011 Byte |
Status | AC |
Exec Time | 507 ms |
Memory | 127180 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_rando_medium_031, 01_rando_medium_035, 01_rando_medium_160, 01_rando_medium_278, 01_rando_medium_337, 01_rando_medium_342, 01_rando_medium_355, 01_rando_medium_452, 01_rando_medium_467, 01_rando_medium_665, 02_rando_large_000, 02_rando_large_013, 02_rando_large_048, 02_rando_large_054, 02_rando_large_083, 02_rando_large_147, 02_rando_large_164, 02_rando_large_227, 02_rando_large_283, 02_rando_large_336, 02_rando_large_368, 05_attack_00, 05_attack_01, 05_attack_mi0803_00, 10_random_small_000, 10_random_small_001, 10_random_small_002, 10_random_small_003, 10_random_small_004, 10_random_small_005, 10_random_small_006, 10_random_small_007, 10_random_small_008, 10_random_small_009, 11_rando_medium_000, 11_rando_medium_001, 11_rando_medium_002, 11_rando_medium_003, 11_rando_medium_004, 11_rando_medium_005, 11_rando_medium_006, 11_rando_medium_007, 11_rando_medium_008, 11_rando_medium_009, 12_random_large_000, 12_random_large_001, 12_random_large_002, 12_random_large_003, 12_random_large_004, 12_random_large_005, 12_random_large_006, 12_random_large_007, 12_random_large_008, 12_random_large_009, 22_shortMusics_Large_000, 22_shortMusics_Large_001, 22_shortMusics_Large_002, 22_shortMusics_Large_003, 22_shortMusics_Large_004, 22_shortMusics_Large_005, 22_shortMusics_Large_006, 22_shortMusics_Large_007, 22_shortMusics_Large_008, 22_shortMusics_Large_009, 41_separate_medium_000, 41_separate_medium_001, 41_separate_medium_002, 41_separate_medium_003, 41_separate_medium_004, 42_separate_large_000, 42_separate_large_001, 42_separate_large_002, 42_separate_large_003, 42_separate_large_004 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sample_03 | AC | 1 ms | 256 KB |
00_sample_04 | AC | 1 ms | 256 KB |
01_rando_medium_031 | AC | 1 ms | 384 KB |
01_rando_medium_035 | AC | 1 ms | 512 KB |
01_rando_medium_160 | AC | 1 ms | 512 KB |
01_rando_medium_278 | AC | 2 ms | 2560 KB |
01_rando_medium_337 | AC | 1 ms | 384 KB |
01_rando_medium_342 | AC | 2 ms | 2560 KB |
01_rando_medium_355 | AC | 1 ms | 512 KB |
01_rando_medium_452 | AC | 2 ms | 2560 KB |
01_rando_medium_467 | AC | 2 ms | 2560 KB |
01_rando_medium_665 | AC | 1 ms | 512 KB |
02_rando_large_000 | AC | 19 ms | 68224 KB |
02_rando_large_013 | AC | 3 ms | 6784 KB |
02_rando_large_048 | AC | 7 ms | 21120 KB |
02_rando_large_054 | AC | 26 ms | 88832 KB |
02_rando_large_083 | AC | 17 ms | 60032 KB |
02_rando_large_147 | AC | 2 ms | 2688 KB |
02_rando_large_164 | AC | 26 ms | 88832 KB |
02_rando_large_227 | AC | 25 ms | 90880 KB |
02_rando_large_283 | AC | 34 ms | 119552 KB |
02_rando_large_336 | AC | 29 ms | 107264 KB |
02_rando_large_368 | AC | 20 ms | 72320 KB |
05_attack_00 | AC | 2 ms | 2688 KB |
05_attack_01 | AC | 2 ms | 640 KB |
05_attack_mi0803_00 | AC | 1 ms | 384 KB |
10_random_small_000 | AC | 1 ms | 256 KB |
10_random_small_001 | AC | 1 ms | 384 KB |
10_random_small_002 | AC | 1 ms | 384 KB |
10_random_small_003 | AC | 1 ms | 384 KB |
10_random_small_004 | AC | 1 ms | 384 KB |
10_random_small_005 | AC | 1 ms | 256 KB |
10_random_small_006 | AC | 1 ms | 384 KB |
10_random_small_007 | AC | 1 ms | 384 KB |
10_random_small_008 | AC | 1 ms | 384 KB |
10_random_small_009 | AC | 1 ms | 384 KB |
11_rando_medium_000 | AC | 1 ms | 512 KB |
11_rando_medium_001 | AC | 1 ms | 512 KB |
11_rando_medium_002 | AC | 1 ms | 384 KB |
11_rando_medium_003 | AC | 2 ms | 2688 KB |
11_rando_medium_004 | AC | 2 ms | 640 KB |
11_rando_medium_005 | AC | 1 ms | 512 KB |
11_rando_medium_006 | AC | 2 ms | 2688 KB |
11_rando_medium_007 | AC | 1 ms | 384 KB |
11_rando_medium_008 | AC | 2 ms | 2688 KB |
11_rando_medium_009 | AC | 1 ms | 384 KB |
12_random_large_000 | AC | 142 ms | 76108 KB |
12_random_large_001 | AC | 131 ms | 58060 KB |
12_random_large_002 | AC | 344 ms | 120268 KB |
12_random_large_003 | AC | 25 ms | 14924 KB |
12_random_large_004 | AC | 224 ms | 127180 KB |
12_random_large_005 | AC | 55 ms | 31180 KB |
12_random_large_006 | AC | 255 ms | 101324 KB |
12_random_large_007 | AC | 17 ms | 11084 KB |
12_random_large_008 | AC | 108 ms | 43980 KB |
12_random_large_009 | AC | 122 ms | 75852 KB |
22_shortMusics_Large_000 | AC | 282 ms | 80588 KB |
22_shortMusics_Large_001 | AC | 262 ms | 100556 KB |
22_shortMusics_Large_002 | AC | 464 ms | 125772 KB |
22_shortMusics_Large_003 | AC | 507 ms | 121932 KB |
22_shortMusics_Large_004 | AC | 371 ms | 113228 KB |
22_shortMusics_Large_005 | AC | 462 ms | 113868 KB |
22_shortMusics_Large_006 | AC | 318 ms | 78924 KB |
22_shortMusics_Large_007 | AC | 394 ms | 91340 KB |
22_shortMusics_Large_008 | AC | 195 ms | 87168 KB |
22_shortMusics_Large_009 | AC | 272 ms | 76620 KB |
41_separate_medium_000 | AC | 1 ms | 640 KB |
41_separate_medium_001 | AC | 2 ms | 2688 KB |
41_separate_medium_002 | AC | 2 ms | 2688 KB |
41_separate_medium_003 | AC | 2 ms | 2688 KB |
41_separate_medium_004 | AC | 2 ms | 2688 KB |
42_separate_large_000 | AC | 59 ms | 95232 KB |
42_separate_large_001 | AC | 70 ms | 74700 KB |
42_separate_large_002 | AC | 55 ms | 72268 KB |
42_separate_large_003 | AC | 94 ms | 117452 KB |
42_separate_large_004 | AC | 67 ms | 78668 KB |