結果
問題 | No.2808 Concentration |
ユーザー | silv723 |
提出日時 | 2024-07-09 22:43:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,815 bytes |
コンパイル時間 | 2,925 ms |
コンパイル使用メモリ | 217,600 KB |
実行使用メモリ | 181,276 KB |
最終ジャッジ日時 | 2024-07-09 22:44:02 |
合計ジャッジ時間 | 16,193 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,752 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 761 ms
74,888 KB |
testcase_04 | AC | 245 ms
30,168 KB |
testcase_05 | AC | 9 ms
5,376 KB |
testcase_06 | AC | 963 ms
99,792 KB |
testcase_07 | AC | 1,117 ms
105,448 KB |
testcase_08 | AC | 670 ms
53,324 KB |
testcase_09 | AC | 1,556 ms
153,544 KB |
testcase_10 | AC | 223 ms
25,640 KB |
testcase_11 | AC | 1,282 ms
134,504 KB |
testcase_12 | AC | 1,408 ms
141,812 KB |
testcase_13 | TLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
testcase_52 | -- | - |
ソースコード
#include<bits/stdc++.h> using namespace std; template <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree { public: dynamic_segtree(size_t n) : n(n), root(nullptr) {} void set(size_t p, S x) { assert(p < n); set(root, 0, n, p, x); } S get(size_t p) const { assert(p < n); return get(root, 0, n, p); } S prod(size_t l, size_t r) const { assert(l <= r && r <= n); return prod(root, 0, n, l, r); } S all_prod() const { return root ? root->product : e(); } void reset(size_t l, size_t r) { assert(l <= r && r <= n); return reset(root, 0, n, l, r); } template <bool (*f)(S)> size_t max_right(size_t l) const { return max_right(l, [](S x) { return f(x); }); } template <class F> size_t max_right(size_t l, const F& f) const { assert(l <= n); S product = e(); assert(f(product)); return max_right(root, 0, n, l, f, product); } template <bool (*f)(S)> size_t min_left(size_t r) const { return min_left(r, [](S x) { return f(x); }); } template <class F> size_t min_left(size_t r, const F& f) const { assert(r <= n); S product = e(); assert(f(product)); return min_left(root, 0, n, r, f, product); } private: struct node; using node_ptr = std::unique_ptr<node>; struct node { size_t index; S value, product; node_ptr left, right; node(size_t index, S value) : index(index), value(value), product(value), left(nullptr), right(nullptr) {} void update() { product = op(op(left ? left->product : e(), value), right ? right->product : e()); } }; const size_t n; node_ptr root; void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const { if (!t) { t = std::make_unique<node>(p, x); return; } if (t->index == p) { t->value = x; t->update(); return; } size_t c = (a + b) >> 1; if (p < c) { if (t->index < p) std::swap(t->index, p), std::swap(t->value, x); set(t->left, a, c, p, x); } else { if (p < t->index) std::swap(p, t->index), std::swap(x, t->value); set(t->right, c, b, p, x); } t->update(); } S get(const node_ptr& t, size_t a, size_t b, size_t p) const { if (!t) return e(); if (t->index == p) return t->value; size_t c = (a + b) >> 1; if (p < c) return get(t->left, a, c, p); else return get(t->right, c, b, p); } S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const { if (!t || b <= l || r <= a) return e(); if (l <= a && b <= r) return t->product; size_t c = (a + b) >> 1; S result = prod(t->left, a, c, l, r); if (l <= t->index && t->index < r) result = op(result, t->value); return op(result, prod(t->right, c, b, l, r)); } void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const { if (!t || b <= l || r <= a) return; if (l <= a && b <= r) { t.reset(); return; } size_t c = (a + b) >> 1; reset(t->left, a, c, l, r); reset(t->right, c, b, l, r); t->update(); } }; using S = long long; S op(S a, S b){ return max(a, b); } S e(){ return 0; }; int main(){ long long n, s, h; cin >> n >> s >> h; vector<int> x(n), y(n), z(n); for(int i = 0; i < n; i++){ cin >> x[i] >> y[i] >> z[i]; } vector<long long> ch; for(int i = 0; i < n; i++){ ch.push_back(x[i]); ch.push_back(y[i]); ch.push_back(x[i]+s); ch.push_back(y[i]+s); ch.push_back(x[i]+h); ch.push_back(y[i]+h); ch.push_back(x[i]-s); ch.push_back(y[i]-s); ch.push_back(x[i]-h); ch.push_back(y[i]-h); ch.push_back(x[i]+s+h); ch.push_back(y[i]+s+h); ch.push_back(x[i]+s-h); ch.push_back(y[i]+s-h); ch.push_back(x[i]-s+h); ch.push_back(y[i]-s+h); ch.push_back(x[i]-s-h); ch.push_back(y[i]-s-h); } sort(ch.begin(), ch.end()); dynamic_segtree<S, op, e> d(1LL<<35); vector<pair<int, int>> p(3); vector<long long> sum(3); for(auto a:ch){ if(a < 0) continue; long long cnt = 0; for(int i = 0; i < 3; i++){ while(a-(s+h)*(i+1) > x[p[i].first] && p[i].first < n){ sum[i] -= z[p[i].first]; p[i].first++; } while(a-(s+h)*(i+1)+s >= y[p[i].second] && p[i].second < n){ sum[i] += z[p[i].second]; p[i].second++; } cnt += sum[i]; long long u = d.prod(0, max(0LL, a-(s+h)*(i+1))) + cnt; d.set(a, max(d.get(a), u)); } } cout << d.prod(0, 1LL<<35) << endl; }