Submission #3274893
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 ConvecHullTrick { private: // 直線群(配列) std::vector<std::pair<T, T>> lines; // 最小値(最大値)を求めるxが単調であるか bool isMonotonicX; // 最小/最大を判断する関数 std::function<bool(T l, T r)> comp; public: // コンストラクタ ( クエリが単調であった場合はflag = trueとする ) ConvecHullTrick(bool flagX = false, std::function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r; }) :isMonotonicX(flagX), comp(compFunc) { }; // 直線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) { static int head = 0; 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 empty() { return lines.size() == 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<ConvecHullTrick<int> > cht; for(int i = 0; i <= T+1; i++) { cht.push_back(ConvecHullTrick<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].empty()) { 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 | 3599 Byte |
Status | RE |
Exec Time | 142 ms |
Memory | 124796 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 | RE | 98 ms | 384 KB |
01_rando_medium_035 | RE | 98 ms | 512 KB |
01_rando_medium_160 | RE | 97 ms | 384 KB |
01_rando_medium_278 | RE | 98 ms | 2560 KB |
01_rando_medium_337 | WA | 1 ms | 384 KB |
01_rando_medium_342 | RE | 98 ms | 2560 KB |
01_rando_medium_355 | RE | 97 ms | 384 KB |
01_rando_medium_452 | RE | 99 ms | 2560 KB |
01_rando_medium_467 | RE | 99 ms | 2560 KB |
01_rando_medium_665 | RE | 97 ms | 512 KB |
02_rando_large_000 | RE | 119 ms | 68224 KB |
02_rando_large_013 | RE | 100 ms | 6656 KB |
02_rando_large_048 | RE | 105 ms | 21120 KB |
02_rando_large_054 | RE | 124 ms | 88704 KB |
02_rando_large_083 | RE | 117 ms | 60032 KB |
02_rando_large_147 | RE | 99 ms | 2560 KB |
02_rando_large_164 | RE | 130 ms | 88704 KB |
02_rando_large_227 | RE | 126 ms | 90752 KB |
02_rando_large_283 | RE | 135 ms | 119424 KB |
02_rando_large_336 | RE | 130 ms | 107136 KB |
02_rando_large_368 | RE | 120 ms | 72320 KB |
05_attack_00 | RE | 99 ms | 2560 KB |
05_attack_01 | RE | 97 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 | WA | 1 ms | 256 KB |
10_random_small_005 | AC | 1 ms | 256 KB |
10_random_small_006 | WA | 1 ms | 256 KB |
10_random_small_007 | AC | 1 ms | 256 KB |
10_random_small_008 | WA | 1 ms | 256 KB |
10_random_small_009 | AC | 1 ms | 256 KB |
11_rando_medium_000 | WA | 1 ms | 384 KB |
11_rando_medium_001 | RE | 99 ms | 512 KB |
11_rando_medium_002 | RE | 99 ms | 384 KB |
11_rando_medium_003 | RE | 99 ms | 2560 KB |
11_rando_medium_004 | RE | 97 ms | 512 KB |
11_rando_medium_005 | RE | 98 ms | 384 KB |
11_rando_medium_006 | RE | 98 ms | 2560 KB |
11_rando_medium_007 | WA | 1 ms | 256 KB |
11_rando_medium_008 | RE | 99 ms | 2560 KB |
11_rando_medium_009 | WA | 1 ms | 384 KB |
12_random_large_000 | RE | 125 ms | 73724 KB |
12_random_large_001 | RE | 119 ms | 55676 KB |
12_random_large_002 | RE | 140 ms | 117372 KB |
12_random_large_003 | RE | 104 ms | 12540 KB |
12_random_large_004 | RE | 142 ms | 124796 KB |
12_random_large_005 | RE | 110 ms | 28796 KB |
12_random_large_006 | RE | 134 ms | 98940 KB |
12_random_large_007 | RE | 104 ms | 8700 KB |
12_random_large_008 | RE | 114 ms | 41596 KB |
12_random_large_009 | RE | 124 ms | 73468 KB |
22_shortMusics_Large_000 | RE | 128 ms | 78204 KB |
22_shortMusics_Large_001 | RE | 132 ms | 98172 KB |
22_shortMusics_Large_002 | RE | 141 ms | 123260 KB |
22_shortMusics_Large_003 | RE | 141 ms | 119420 KB |
22_shortMusics_Large_004 | RE | 137 ms | 110844 KB |
22_shortMusics_Large_005 | RE | 138 ms | 111228 KB |
22_shortMusics_Large_006 | RE | 127 ms | 76412 KB |
22_shortMusics_Large_007 | RE | 134 ms | 88700 KB |
22_shortMusics_Large_008 | RE | 128 ms | 85760 KB |
22_shortMusics_Large_009 | RE | 125 ms | 74236 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 | 1 ms | 2688 KB |
42_separate_large_000 | WA | 56 ms | 93952 KB |
42_separate_large_001 | WA | 60 ms | 72316 KB |
42_separate_large_002 | WA | 50 ms | 69884 KB |
42_separate_large_003 | WA | 84 ms | 115068 KB |
42_separate_large_004 | WA | 60 ms | 76284 KB |