Submission #3274499
Source Code Expand
#include <bits/stdc++.h> using namespace std; using LL = long long int; #define int long long const int MAX_N = 4005; const int MAX_T = 4005; template<typename T> class ConvexHullTrick { private: // 直線群(配列) std::vector<std::pair<T, T>> lines; // 最小値(最大値)を求めるxが単調であるか bool isMonotonicX; // 最小/最大を判断する関数 std::function<bool(T l, T r)> comp; public: // コンストラクタ ( クエリが単調であった場合はflag = trueとする ) ConvexHullTrick(bool flagX = true, std::function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r; }) :isMonotonicX(flagX), comp(compFunc) { // lines.emplace_back(-114514, -114514); }; // 直線l1, l2, l3のうちl2が不必要であるかどうか bool check(std::pair<T, T> l1, std::pair<T, T> l2, std::pair<T, T> l3) { if (l1 < l3) std::swap(l1, l3); return (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first); } // 直線y=ax+bを追加する void add(T a, T b) { std::pair<T, T> line(a, b); while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), line)) lines.pop_back(); lines.emplace_back(line); } // i番目の直線f_i(x)に対するxの時の値を返す T f(int i, T x) { return lines[i].first * x + lines[i].second; } // i番目の直線f_i(x)に対するxの時の値を返す T f(std::pair<T, T> line, T x) { return line.first * x + line.second; } // 直線群の中でxの時に最小(最大)となる値を返す T get(T x) { // 最小値(最大値)クエリにおけるxが単調 if (isMonotonicX) { while (lines.size() - head >= 2 && comp(f(head, x), f(head + 1, x))) ++head; return f(head, x); } else { int low = -1, high = lines.size() - 1; while (high - low > 1) { int mid = (high + low) / 2; (comp(f(mid, x), f(mid + 1, x)) ? low : high) = mid; } return f(high, x); } } bool isContains() { return lines.size() > 0; } int head = 0; }; 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<ConvexHullTrick<int> > cht; for(int i = 0; i <= T; i++) { cht.push_back(ConvexHullTrick<int>(true, less<int>())); } int ans = 0; 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] = song.p; } else { if(!cht[t-song.t].isContains()) { continue; } dp[i][t] = max(dp[i][t], song.p - song.f * song.f + cht[t-song.t].get(song.f)); } cht[t].add(2*song.f, dp[i][t] - song.f*song.f); ans = max(ans, dp[i][t]); // cerr << i << " " << t << " " << dp[i][t] << endl; } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | I - Live Programming |
User | takoshi |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3309 Byte |
Status | WA |
Exec Time | 602 ms |
Memory | 142172 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | WA | 1 ms | 384 KB |
01_rando_medium_035 | WA | 1 ms | 512 KB |
01_rando_medium_160 | WA | 1 ms | 512 KB |
01_rando_medium_278 | WA | 2 ms | 2560 KB |
01_rando_medium_337 | WA | 1 ms | 384 KB |
01_rando_medium_342 | WA | 2 ms | 2560 KB |
01_rando_medium_355 | WA | 1 ms | 384 KB |
01_rando_medium_452 | WA | 2 ms | 2560 KB |
01_rando_medium_467 | WA | 2 ms | 2560 KB |
01_rando_medium_665 | WA | 1 ms | 512 KB |
02_rando_large_000 | WA | 18 ms | 68224 KB |
02_rando_large_013 | WA | 3 ms | 6784 KB |
02_rando_large_048 | WA | 6 ms | 21120 KB |
02_rando_large_054 | WA | 25 ms | 88704 KB |
02_rando_large_083 | WA | 16 ms | 60160 KB |
02_rando_large_147 | WA | 2 ms | 2560 KB |
02_rando_large_164 | WA | 24 ms | 88704 KB |
02_rando_large_227 | WA | 24 ms | 90752 KB |
02_rando_large_283 | WA | 33 ms | 119936 KB |
02_rando_large_336 | WA | 28 ms | 107392 KB |
02_rando_large_368 | WA | 19 ms | 72448 KB |
05_attack_00 | WA | 2 ms | 2560 KB |
05_attack_01 | WA | 1 ms | 512 KB |
05_attack_mi0803_00 | WA | 1 ms | 384 KB |
10_random_small_000 | AC | 1 ms | 256 KB |
10_random_small_001 | AC | 1 ms | 256 KB |
10_random_small_002 | AC | 1 ms | 256 KB |
10_random_small_003 | AC | 1 ms | 256 KB |
10_random_small_004 | AC | 1 ms | 256 KB |
10_random_small_005 | AC | 1 ms | 256 KB |
10_random_small_006 | AC | 1 ms | 256 KB |
10_random_small_007 | AC | 1 ms | 256 KB |
10_random_small_008 | AC | 1 ms | 256 KB |
10_random_small_009 | AC | 1 ms | 256 KB |
11_rando_medium_000 | AC | 1 ms | 384 KB |
11_rando_medium_001 | WA | 1 ms | 512 KB |
11_rando_medium_002 | WA | 1 ms | 384 KB |
11_rando_medium_003 | WA | 2 ms | 2560 KB |
11_rando_medium_004 | WA | 1 ms | 512 KB |
11_rando_medium_005 | WA | 1 ms | 384 KB |
11_rando_medium_006 | WA | 2 ms | 2560 KB |
11_rando_medium_007 | AC | 1 ms | 256 KB |
11_rando_medium_008 | WA | 2 ms | 2560 KB |
11_rando_medium_009 | AC | 1 ms | 384 KB |
12_random_large_000 | WA | 139 ms | 80476 KB |
12_random_large_001 | WA | 126 ms | 60892 KB |
12_random_large_002 | WA | 349 ms | 131676 KB |
12_random_large_003 | WA | 21 ms | 12380 KB |
12_random_large_004 | WA | 219 ms | 131804 KB |
12_random_large_005 | WA | 51 ms | 31324 KB |
12_random_large_006 | WA | 255 ms | 108508 KB |
12_random_large_007 | WA | 13 ms | 8284 KB |
12_random_large_008 | WA | 110 ms | 50140 KB |
12_random_large_009 | WA | 118 ms | 79196 KB |
22_shortMusics_Large_000 | WA | 329 ms | 94812 KB |
22_shortMusics_Large_001 | WA | 295 ms | 110172 KB |
22_shortMusics_Large_002 | WA | 547 ms | 142172 KB |
22_shortMusics_Large_003 | WA | 602 ms | 140380 KB |
22_shortMusics_Large_004 | WA | 418 ms | 129244 KB |
22_shortMusics_Large_005 | WA | 545 ms | 133212 KB |
22_shortMusics_Large_006 | WA | 368 ms | 94556 KB |
22_shortMusics_Large_007 | WA | 457 ms | 110172 KB |
22_shortMusics_Large_008 | WA | 239 ms | 98160 KB |
22_shortMusics_Large_009 | WA | 302 ms | 92764 KB |
41_separate_medium_000 | WA | 1 ms | 512 KB |
41_separate_medium_001 | WA | 2 ms | 2560 KB |
41_separate_medium_002 | WA | 1 ms | 2560 KB |
41_separate_medium_003 | WA | 1 ms | 2560 KB |
41_separate_medium_004 | WA | 2 ms | 2560 KB |
42_separate_large_000 | WA | 30 ms | 93040 KB |
42_separate_large_001 | WA | 30 ms | 70620 KB |
42_separate_large_002 | WA | 25 ms | 68444 KB |
42_separate_large_003 | WA | 42 ms | 113628 KB |
42_separate_large_004 | WA | 30 ms | 74716 KB |