結果
問題 | No.777 再帰的ケーキ |
ユーザー | walkre |
提出日時 | 2018-12-24 03:21:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,026 bytes |
コンパイル時間 | 2,356 ms |
コンパイル使用メモリ | 196,776 KB |
実行使用メモリ | 40,248 KB |
最終ジャッジ日時 | 2024-09-25 10:56:22 |
合計ジャッジ時間 | 5,842 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | WA | - |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | WA | - |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 4 ms
6,940 KB |
testcase_22 | AC | 3 ms
6,940 KB |
testcase_23 | AC | 3 ms
6,944 KB |
testcase_24 | AC | 3 ms
6,940 KB |
testcase_25 | AC | 4 ms
6,940 KB |
testcase_26 | AC | 4 ms
6,944 KB |
testcase_27 | AC | 3 ms
6,940 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | AC | 211 ms
40,120 KB |
testcase_33 | AC | 95 ms
26,532 KB |
testcase_34 | AC | 119 ms
30,076 KB |
testcase_35 | WA | - |
testcase_36 | AC | 208 ms
40,132 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64=int64_t; #define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i) #define debug(x) #x << "=" << (x) #ifdef DEBUG #define _GLIBCXX_DEBUG #define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl #else #define print(x) #endif const int inf=1.01e9; const i64 inf64=4.01e18; const double eps=1e-9; template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (const auto &v : vec) { os << v << ","; } os << "]"; return os; } template <class T, T op(T, T)> class segtree { public: int n, size_; vector<T> dat; T id_; segtree() = default; segtree(int size, T id, T initial_value) { init(size, id, initial_value); } void init(int size, T id, T initial_value) { size_ = size; id_ = id; n = 1; while (n < size) n *= 2; dat.assign(2 * n - 1, id); for (int i = 0; i < size; ++i) update(i, initial_value); } int size() const { return size_; } void update(int k, T a) { k += n - 1; // leaf dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = op(dat[k * 2 + 1], dat[k * 2 + 2]); } } T at(int index) { return dat[index + n - 1]; } void add(int k, T a) { update(k, at(k) + a); } T query(int a, int b) { return query(a, b, 0, 0, n); } T query(int a, int b, int k, int l, int r) { if (r <= a or b <= l) return id_; if (a <= l and r <= b) return dat[k]; int m = (l + r) / 2; return op(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r)); } }; i64 mymax(i64 a,i64 b){ return max(a,b); } void solve(){ i64 N; cin >> N; vector<tuple<i64,i64,i64>> ABC(N); rep(i,0,N){ i64 A,B,C; cin >> A >> B >> C; ABC[i]=make_tuple(A,B,C); } sort(begin(ABC),end(ABC)); vector<pair<i64,i64>> bi(N); rep(i,0,N) bi[i]=make_pair(get<1>(ABC[i]),i); sort(begin(bi),end(bi)); vector<i64> rev1(N),rev2(N); { i64 j=0; rep(i, 0, N){ rev1[bi[i].second] = i; if(i and bi[i].first>bi[i-1].first) ++j; rev2[bi[i].second]=j; } } segtree<i64,mymax> seg(N,0,-inf64); map<i64,vector<tuple<i64,i64,i64>>> mp; rep(i,0,N){ i64 a,b,c; tie(a,b,c)=ABC[i]; mp[a].push_back(make_tuple(b,c,i)); } for(const auto& p:mp){ vector<pair<i64,i64>> iv; for(const auto& t:p.second){ i64 b,c,i; tie(b,c,i)=t; i64 tmp=max(i64(0),seg.query(0,rev2[i])); iv.push_back(make_pair(rev1[i],tmp+c)); } for(auto& tmp:iv) seg.update(tmp.first,tmp.second); } cout << seg.query(0,N) << endl; } int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); solve(); return 0; }