結果
問題 | No.777 再帰的ケーキ |
ユーザー |
|
提出日時 | 2019-05-06 03:06:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 1,662 bytes |
コンパイル時間 | 1,771 ms |
コンパイル使用メモリ | 183,968 KB |
実行使用メモリ | 18,048 KB |
最終ジャッジ日時 | 2024-06-26 10:13:11 |
合計ジャッジ時間 | 5,557 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Cake{int a, b, c;bool operator<(const Cake& right) const{return a == right.a ? b > right.b : a < right.a;}};void select_cakes(vector<Cake> & src){int j = 0;for (int i = 1; i < src.size(); ++i){if (src[j].a == src[i].a and src[j].b == src[i].b){src[j].c = max(src[j].c, src[i].c);}else{++j;src[j] = src[i];}}src.erase(src.begin()+j+1, src.end());return;}int main(){cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<Cake> cakes(N, Cake{0, 0, 0});for (auto & cake : cakes) cin >> cake.a >> cake.b >> cake.c;sort(cakes.begin(), cakes.end());select_cakes(cakes);map<int, long long> dp;dp[0] = 0LL;for (auto & cake : cakes){auto it = dp.upper_bound(cake.b);--it;if (it->first == cake.b){--it;long long val = it->second + cake.c;++it;if (it->second >= val){continue;}else{it->second = val;++it;auto jt = it;while (jt != dp.end() and jt->second <= val) ++jt;dp.erase(it, jt);}}else{long long val = it->second + cake.c;dp[cake.b] = val;auto it = dp.find(cake.b);++it;auto jt = it;while (jt != dp.end() and jt->second <= val) ++jt;dp.erase(it, jt);}}cout << dp.rbegin()->second << endl;return 0;}