結果
問題 | No.777 再帰的ケーキ |
ユーザー | tarakojo1019 |
提出日時 | 2021-01-18 19:47:38 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,101 ms / 2,000 ms |
コード長 | 2,849 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 137,672 KB |
実行使用メモリ | 51,096 KB |
最終ジャッジ日時 | 2024-12-14 10:57:35 |
合計ジャッジ時間 | 9,732 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,816 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,820 KB |
testcase_15 | AC | 2 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 2 ms
6,816 KB |
testcase_21 | AC | 6 ms
6,820 KB |
testcase_22 | AC | 6 ms
6,816 KB |
testcase_23 | AC | 3 ms
6,820 KB |
testcase_24 | AC | 3 ms
6,816 KB |
testcase_25 | AC | 6 ms
6,820 KB |
testcase_26 | AC | 6 ms
6,816 KB |
testcase_27 | AC | 3 ms
6,820 KB |
testcase_28 | AC | 1,041 ms
51,008 KB |
testcase_29 | AC | 1,033 ms
51,056 KB |
testcase_30 | AC | 1,101 ms
51,052 KB |
testcase_31 | AC | 1,092 ms
51,060 KB |
testcase_32 | AC | 540 ms
51,096 KB |
testcase_33 | AC | 111 ms
7,356 KB |
testcase_34 | AC | 166 ms
7,124 KB |
testcase_35 | AC | 649 ms
29,132 KB |
testcase_36 | AC | 539 ms
51,060 KB |
ソースコード
#include<iostream> #include<math.h> #include<algorithm> #include<stdint.h> #include<vector> #include<deque> #include<stack> #include<functional> #include<string> #include<numeric> #include<cstring> #include<random> #include<array> #include<fstream> #include<iomanip> #include<list> #include<set> #include<map> #include<unordered_map> #include<unordered_set> #include<bitset> #include<queue> /* #include<boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; */ using namespace std; using ll = long long; using ull = unsigned long long; #define REP(i,a,b) for(ll i = a; i < b; ++i) #define PRI(s) std::cout << s << endl #define PRIF(v, n) printf("%."#n"f\n", (double)v) template<typename A, typename B>void mins(A& a, const B& b) { a = min(a, (A)b); }; template<typename A, typename B>void maxs(A& a, const B& b) { a = max(a, (A)b); }; template<typename X> class segtree { public: using func_xx = function<X(X, X)>; long long N; func_xx fxx; X ex; vector<X> dat; bool changed; segtree() {} segtree(long long n, func_xx fxx, const X& ex) : fxx(fxx), ex(ex), changed(false) { if (n == 1) ++n; int x = 1; while (x < n) x *= 2; N = x; dat.resize(2 * N - 1, ex); } const segtree<X>& operator=(const segtree& source) { N = source.N; fxx = source.fxx; ex = source.ex; dat = source.dat; changed = source.changed; return *this; } //代入後のデータ更新 void update(int k) { dat[k] = fxx(dat[2 * k + 1], dat[2 * k + 2]); if (k != 0) update((k - 1) / 2); } void build() { for (int i = N - 2; i >= 0; --i) dat[i] = fxx(dat[2 * i + 1], dat[2 * i + 2]); changed = false; } //要素の代入 void set(int i, const X& x, bool update = true) { dat[N - 1 + i] = x; if (update) this->update((N - 2 + i) / 2); else changed = true; } //要素の参照 const X& elem(int i) { return dat[N - 1 + i]; } X query_sub(int a, int b, int k, int l, int r) { if (r <= a || b <= l) { return ex; } else if (a <= l && r <= b) { return dat[k]; } else { return fxx(query_sub(a, b, 2 * k + 1, l, (l + r) / 2), query_sub(a, b, 2 * k + 2, (l + r) / 2, r)); } } //[a,b)間のクエリfxx X query(int a, int b) { if (changed) build(); return query_sub(a, b, 0, 0, N); } }; int main() { auto func = [](ll a, ll b) {return max(a, b); }; ll N; cin >> N; map<ll, map <ll, ll, greater<ll>>> mp; map<ll, ll> ind; REP(i, 0, N) { ll a, b, c; cin >> a >> b >> c; if (mp.count(a) != 0 && mp[a].count(b) != 0 && mp[a][b] >= c) continue; mp[a][b] = c; ind[b] = 0; } ll c = 0; for (auto& p : ind) p.second = c++; segtree<ll> seg{ N, func, 0 }; for (auto& v : mp) { for (auto p : v.second) { ll tmp = seg.query(0, ind[p.first]); if (seg.elem(ind[p.first]) < tmp + p.second) seg.set(ind[p.first], tmp + p.second); } } PRI(seg.query(0, N)); return 0; }