Submission #3274630
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<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+1; i++) { cht.push_back(ConvexHullTrick<int>(true)); } 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].isContains()) { continue; } dp[i][t] = max(dp[i][t], song.p - song.f * song.f - cht[t-song.t].get(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 | 0 |
Code Size | 3646 Byte |
Status | WA |
Exec Time | 531 ms |
Memory | 125788 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 | 3 ms | 512 KB |
01_rando_medium_035 | AC | 1 ms | 512 KB |
01_rando_medium_160 | AC | 1 ms | 384 KB |
01_rando_medium_278 | AC | 2 ms | 2560 KB |
01_rando_medium_337 | AC | 1 ms | 384 KB |
01_rando_medium_342 | AC | 1 ms | 2560 KB |
01_rando_medium_355 | WA | 1 ms | 512 KB |
01_rando_medium_452 | AC | 2 ms | 2560 KB |
01_rando_medium_467 | AC | 1 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 | 7 ms | 21120 KB |
02_rando_large_054 | WA | 25 ms | 88704 KB |
02_rando_large_083 | WA | 16 ms | 60032 KB |
02_rando_large_147 | WA | 2 ms | 2560 KB |
02_rando_large_164 | WA | 25 ms | 88704 KB |
02_rando_large_227 | WA | 25 ms | 90752 KB |
02_rando_large_283 | WA | 33 ms | 119552 KB |
02_rando_large_336 | WA | 28 ms | 107136 KB |
02_rando_large_368 | WA | 20 ms | 72320 KB |
05_attack_00 | WA | 2 ms | 2560 KB |
05_attack_01 | WA | 1 ms | 512 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 | 256 KB |
10_random_small_002 | AC | 1 ms | 384 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 | AC | 1 ms | 512 KB |
11_rando_medium_002 | AC | 1 ms | 384 KB |
11_rando_medium_003 | WA | 2 ms | 2560 KB |
11_rando_medium_004 | AC | 1 ms | 512 KB |
11_rando_medium_005 | AC | 1 ms | 384 KB |
11_rando_medium_006 | AC | 2 ms | 2560 KB |
11_rando_medium_007 | AC | 1 ms | 256 KB |
11_rando_medium_008 | WA | 2 ms | 2688 KB |
11_rando_medium_009 | AC | 1 ms | 384 KB |
12_random_large_000 | WA | 123 ms | 74588 KB |
12_random_large_001 | WA | 114 ms | 56796 KB |
12_random_large_002 | WA | 302 ms | 119004 KB |
12_random_large_003 | WA | 21 ms | 13020 KB |
12_random_large_004 | WA | 201 ms | 125788 KB |
12_random_large_005 | WA | 46 ms | 29404 KB |
12_random_large_006 | WA | 228 ms | 100188 KB |
12_random_large_007 | WA | 14 ms | 9308 KB |
12_random_large_008 | WA | 94 ms | 42460 KB |
12_random_large_009 | WA | 107 ms | 74204 KB |
22_shortMusics_Large_000 | WA | 289 ms | 79964 KB |
22_shortMusics_Large_001 | WA | 263 ms | 99420 KB |
22_shortMusics_Large_002 | WA | 474 ms | 125148 KB |
22_shortMusics_Large_003 | WA | 531 ms | 121692 KB |
22_shortMusics_Large_004 | WA | 373 ms | 112476 KB |
22_shortMusics_Large_005 | WA | 478 ms | 113244 KB |
22_shortMusics_Large_006 | WA | 327 ms | 78428 KB |
22_shortMusics_Large_007 | WA | 406 ms | 90844 KB |
22_shortMusics_Large_008 | WA | 216 ms | 86896 KB |
22_shortMusics_Large_009 | WA | 279 ms | 75868 KB |
41_separate_medium_000 | AC | 1 ms | 512 KB |
41_separate_medium_001 | AC | 2 ms | 2560 KB |
41_separate_medium_002 | AC | 1 ms | 2560 KB |
41_separate_medium_003 | AC | 2 ms | 2560 KB |
41_separate_medium_004 | AC | 2 ms | 2688 KB |
42_separate_large_000 | AC | 46 ms | 94064 KB |
42_separate_large_001 | AC | 51 ms | 72284 KB |
42_separate_large_002 | AC | 41 ms | 69852 KB |
42_separate_large_003 | AC | 70 ms | 115036 KB |
42_separate_large_004 | WA | 49 ms | 76380 KB |