結果
問題 | No.777 再帰的ケーキ |
ユーザー |
|
提出日時 | 2019-01-27 19:13:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 397 ms / 2,000 ms |
コード長 | 2,598 bytes |
コンパイル時間 | 2,165 ms |
コンパイル使用メモリ | 193,024 KB |
実行使用メモリ | 31,588 KB |
最終ジャッジ日時 | 2024-09-25 02:27:44 |
合計ジャッジ時間 | 6,104 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#define _USE_MATH_DEFINES#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define MT make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define RT returnusing ll = long long;using pii = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;template<class Val, class Cmp>class DynamicRMQ {int n;Val init;vector<Val> dat;Cmp cmp;inline Val query(int a, int b, int k, int l, int r) {if (r <= a || b <= l) return init;if (a <= l && r <= b) return dat[k];else {Val vl, vr;vl = query(a, b, k << 1, l, (l + r) >> 1);vr = query(a, b, (k << 1) | 1, (l + r) >> 1, r);return cmp(vl, vr) ? vl : vr;}}public:DynamicRMQ() {}DynamicRMQ(int n_, Val init_) :n(1), init(init_) {for (; n<n_; n <<= 1);dat = vector<Val>(n << 1, init);}void update(int k, Val a) {k += n;dat[k] = a;while (k > 1) {k >>= 1;dat[k] = cmp(dat[k << 1], dat[(k << 1) | 1]) ? dat[k << 1] : dat[(k << 1) | 1];}}Val query(int a, int b) {return query(a, b, 1, 0, n);}};typedef DynamicRMQ<long long, less<long long> > RMinQ64;typedef DynamicRMQ<long long, greater<long long> > RMaxQ64;typedef DynamicRMQ<int, less<int> > RMinQ32;typedef DynamicRMQ<int, greater<int> > RMaxQ32;template<class Val>vector<Val> compress(vector<Val> &v) {vector<Val> a = v;sort(all(a));a.erase(unique(all(a)), a.end());each(b, v)b = (int)(lower_bound(all(a), b) - a.begin());return a;}void solve() {int N;cin >> N;vi A(N), B(N), C(N);rep(i, N) {cin >> A[i] >> B[i] >> C[i];}compress(B);map<int, vector<pii>> M;rep(i, N) {M[A[i]].emplace_back(B[i], C[i]);}RMaxQ64 ma(N + 1, 0ll);each(p, M) {auto &V = p.second;sort(V.rbegin(), V.rend());each(q, V) {ma.update(q.first + 1,max(ma.query(q.first+1,q.first+2),ma.query(0, q.first + 1) + q.second));}}cout << ma.query(0, N + 1) << endl;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);solve();return 0;}