結果
問題 | No.2808 Concentration |
ユーザー | ruthen |
提出日時 | 2024-07-13 01:15:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 17,015 bytes |
コンパイル時間 | 2,358 ms |
コンパイル使用メモリ | 156,684 KB |
実行使用メモリ | 28,736 KB |
最終ジャッジ日時 | 2024-07-13 01:15:20 |
合計ジャッジ時間 | 12,246 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 212 ms
22,712 KB |
testcase_01 | AC | 228 ms
22,980 KB |
testcase_02 | AC | 169 ms
22,544 KB |
testcase_03 | AC | 178 ms
22,844 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 73 ms
12,372 KB |
testcase_08 | AC | 29 ms
7,540 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 106 ms
18,992 KB |
testcase_11 | AC | 139 ms
17,732 KB |
testcase_12 | AC | 46 ms
8,448 KB |
testcase_13 | AC | 162 ms
25,560 KB |
testcase_14 | AC | 24 ms
6,944 KB |
testcase_15 | AC | 137 ms
24,932 KB |
testcase_16 | AC | 149 ms
24,248 KB |
testcase_17 | AC | 178 ms
22,012 KB |
testcase_18 | AC | 164 ms
28,372 KB |
testcase_19 | AC | 83 ms
14,420 KB |
testcase_20 | AC | 171 ms
26,116 KB |
testcase_21 | AC | 136 ms
22,576 KB |
testcase_22 | AC | 118 ms
16,312 KB |
testcase_23 | AC | 85 ms
17,076 KB |
testcase_24 | AC | 157 ms
23,152 KB |
testcase_25 | AC | 89 ms
14,864 KB |
testcase_26 | AC | 165 ms
21,888 KB |
testcase_27 | AC | 184 ms
24,452 KB |
testcase_28 | AC | 243 ms
28,464 KB |
testcase_29 | AC | 166 ms
28,664 KB |
testcase_30 | AC | 175 ms
28,736 KB |
testcase_31 | AC | 155 ms
27,152 KB |
testcase_32 | AC | 157 ms
28,348 KB |
testcase_33 | AC | 201 ms
28,224 KB |
testcase_34 | AC | 165 ms
27,096 KB |
testcase_35 | AC | 166 ms
24,636 KB |
testcase_36 | AC | 171 ms
27,128 KB |
testcase_37 | AC | 201 ms
24,260 KB |
testcase_38 | AC | 171 ms
26,996 KB |
testcase_39 | AC | 163 ms
23,072 KB |
testcase_40 | AC | 166 ms
24,632 KB |
testcase_41 | AC | 171 ms
28,400 KB |
testcase_42 | AC | 182 ms
24,664 KB |
testcase_43 | AC | 223 ms
26,812 KB |
testcase_44 | AC | 165 ms
22,684 KB |
testcase_45 | AC | 162 ms
25,776 KB |
testcase_46 | AC | 163 ms
24,724 KB |
testcase_47 | AC | 2 ms
6,940 KB |
testcase_48 | AC | 2 ms
6,940 KB |
testcase_49 | AC | 2 ms
6,944 KB |
testcase_50 | AC | 2 ms
6,940 KB |
testcase_51 | AC | 2 ms
6,944 KB |
testcase_52 | AC | 3 ms
6,944 KB |
testcase_53 | AC | 2 ms
6,944 KB |
testcase_54 | AC | 2 ms
6,940 KB |
testcase_55 | AC | 2 ms
6,944 KB |
testcase_56 | AC | 2 ms
6,940 KB |
ソースコード
// #include "my_template.hpp" // #include "data_structure/segment_tree.hpp" // #include "algebra/monoid_s/monoid_max.hpp" // using namespace std; // // void solve() { // I64(N, S, H); // VEC3(i64, X, Y, Z, N); // vector<i64> cum(N + 1); // REP(i, N) cum[i + 1] = cum[i] + Z[i]; // // dp[i + 1] = 話 i を聞き終えた時点での得られた知識の最大値 // SegmentTree<MonoidMax<i64>> dp(N + 1); // dp.set(0, 0); // multiset<i64> st; // st.insert(-INF<i64>); // vector<vector<i64>> event(N + 1); // REP(i, N) { // // i 番目の話からいくつか連続で聞き始める (配る) // // {i}, {i, i+1}, {i, i+1, i+2}, ... とすべて列挙すると間に合わないので // // 聞く話の集合のの右端のところまで計算を先送りにする // // // 先送りにした分の計算 // dp.chset(i, *st.rbegin() + cum[i]); // // // どの話まで聞けるか: 遷移先 (dp[r] の計算までは含めて良い) // int r = UB(Y, X[i] + S); // // どこから寝る必要があるか: 遷移元 (dp[l] の計算までは含めて良い) // int l = UB(Y, X[i] - H); // i64 mx = dp.prod(0, l + 1); // max(dp[0], dp[1], ... , dp[l]) // // st.insert(mx - cum[i]); // event[r].push_back(mx - cum[i]); // // // r = i の場合に備えてここで無効になった先送り分を反映させる // FORE(val, event[i]) st.extract(val); // } // dp.chset(N, *st.rbegin() + cum[N]); // // FORE(val, event[N]) st.extract(val); // i64 ans = dp.all_prod(); // print(ans); // return; // } // // int main() { // solve(); // return 0; // } #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <deque> #include <forward_list> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iostream> #include <limits> #include <list> #include <map> #include <memory> #include <numeric> #include <optional> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <type_traits> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #ifdef RUTHEN_LOCAL #include <debug.hpp> #else #define show(x) true #endif // type definition using i64 = long long; using u32 = unsigned int; using u64 = unsigned long long; using f32 = float; using f64 = double; using f128 = long double; template <class T> using pque = std::priority_queue<T>; template <class T> using pqueg = std::priority_queue<T, std::vector<T>, std::greater<T>>; // overload #define overload4(_1, _2, _3, _4, name, ...) name #define overload3(_1, _2, _3, name, ...) name #define overload2(_1, _2, name, ...) name // for loop #define REP1(a) for (long long _ = 0; _ < (a); _++) #define REP2(i, a) for (long long i = 0; i < (a); i++) #define REP3(i, a, b) for (long long i = (a); i < (b); i++) #define REP4(i, a, b, c) for (long long i = (a); i < (b); i += (c)) #define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define RREP1(a) for (long long _ = (a)-1; _ >= 0; _--) #define RREP2(i, a) for (long long i = (a)-1; i >= 0; i--) #define RREP3(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define RREP(...) overload3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__) #define FORE1(x, a) for (auto&& x : a) #define FORE2(x, y, a) for (auto&& [x, y] : a) #define FORE3(x, y, z, a) for (auto&& [x, y, z] : a) #define FORE(...) overload4(__VA_ARGS__, FORE3, FORE2, FORE1)(__VA_ARGS__) #define FORSUB(t, s) for (long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) // function #define ALL(a) (a).begin(), (a).end() #define RALL(a) (a).rbegin(), (a).rend() #define SORT(a) std::sort((a).begin(), (a).end()) #define RSORT(a) std::sort((a).rbegin(), (a).rend()) #define REV(a) std::reverse((a).begin(), (a).end()) #define UNIQUE(a) \ std::sort((a).begin(), (a).end()); \ (a).erase(std::unique((a).begin(), (a).end()), (a).end()) #define LEN(a) (int)((a).size()) #define MIN(a) *std::min_element((a).begin(), (a).end()) #define MAX(a) *std::max_element((a).begin(), (a).end()) #define SUM1(a) std::accumulate((a).begin(), (a).end(), 0LL) #define SUM2(a, x) std::accumulate((a).begin(), (a).end(), (x)) #define SUM(...) overload2(__VA_ARGS__, SUM2, SUM1)(__VA_ARGS__) #define LB(a, x) std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x))) #define UB(a, x) std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x))) template <class T, class U> inline bool chmin(T& a, const U& b) { return (a > T(b) ? a = b, 1 : 0); } template <class T, class U> inline bool chmax(T& a, const U& b) { return (a < T(b) ? a = b, 1 : 0); } template <class T, class S> inline T floor(const T x, const S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1))); } template <class T, class S> inline T ceil(const T x, const S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); } template <class T, class S> std::pair<T, T> inline divmod(const T x, const S y) { T q = floor(x, y); return {q, x - q * y}; } // 10 ^ n constexpr long long TEN(int n) { return (n == 0) ? 1 : 10LL * TEN(n - 1); } // 1 + 2 + ... + n #define TRI1(n) ((n) * ((n) + 1LL) / 2) // l + (l + 1) + ... + r #define TRI2(l, r) (((l) + (r)) * ((r) - (l) + 1LL) / 2) #define TRI(...) overload2(__VA_ARGS__, TRI2, TRI1)(__VA_ARGS__) // bit operation // bit[i] (= 0 or 1) #define IBIT(bit, i) (((bit) >> (i)) & 1) // (0, 1, 2, 3, 4) -> (0, 1, 3, 7, 15) #define MASK(n) ((1LL << (n)) - 1) #define POW2(n) (1LL << (n)) // (0, 1, 2, 3, 4) -> (0, 1, 1, 2, 1) int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(i64 x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(i64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(i64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } // binary search (integer) template <class T, class F> T bin_search(T ok, T ng, F& f) { while ((ok > ng ? ok - ng : ng - ok) > 1) { T md = (ng + ok) >> 1; (f(md) ? ok : ng) = md; } return ok; } // binary search (real number) template <class T, class F> T bin_search_real(T ok, T ng, F& f, const int iter = 100) { for (int _ = 0; _ < iter; _++) { T md = (ng + ok) / 2; (f(md) ? ok : ng) = md; } return ok; } // floor(sqrt(x)) template <class T> constexpr T sqrt_floor(T x) { return T(sqrtl(x)); } // check if [l1, r1) and [l2, r2) intersect template <class T> constexpr bool intersect(const T l1, const T r1, const T l2, const T r2) { return std::max(l1, l2) < std::min(r1, r2); } // check if [a.first, a.second) and [b.first, b.second) intersect template <class T> constexpr bool intersect(const std::pair<T, T>& a, const std::pair<T, T>& b) { return intersect(a.first, a.second, b.first, b.second); } // rotate matrix counterclockwise by pi / 2 template <class T> void rot(std::vector<std::vector<T>>& a) { if ((int)(a.size()) == 0) return; if ((int)(a[0].size()) == 0) return; int n = (int)(a.size()), m = (int)(a[0].size()); std::vector res(m, std::vector<T>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { res[m - 1 - j][i] = a[i][j]; } } a.swap(res); } // const value constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; // infinity template <class T> constexpr T INF = 0; template <> constexpr int INF<int> = 1'000'000'000; // 1e9 template <> constexpr i64 INF<i64> = i64(INF<int>) * INF<int> * 2; // 2e18 template <> constexpr u32 INF<u32> = INF<int>; // 1e9 template <> constexpr u64 INF<u64> = INF<i64>; // 2e18 template <> constexpr f32 INF<f32> = INF<i64>; // 2e18 template <> constexpr f64 INF<f64> = INF<i64>; // 2e18 template <> constexpr f128 INF<f128> = INF<i64>; // 2e18 // I/O // input template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto&& i : v) is >> i; return is; } template <class... T> void in(T&... a) { (std::cin >> ... >> a); } void scan() {} template <class Head, class... Tail> void scan(Head& head, Tail&... tail) { in(head); scan(tail...); } // input macro #define INT(...) \ int __VA_ARGS__; \ scan(__VA_ARGS__) #define I64(...) \ i64 __VA_ARGS__; \ scan(__VA_ARGS__) #define U32(...) \ u32 __VA_ARGS__; \ scan(__VA_ARGS__) #define U64(...) \ u64 __VA_ARGS__; \ scan(__VA_ARGS__) #define F32(...) \ f32 __VA_ARGS__; \ scan(__VA_ARGS__) #define F64(...) \ f64 __VA_ARGS__; \ scan(__VA_ARGS__) #define F128(...) \ f128 __VA_ARGS__; \ scan(__VA_ARGS__) #define STR(...) \ std::string __VA_ARGS__; \ scan(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ scan(__VA_ARGS__) #define VEC(type, name, size) \ std::vector<type> name(size); \ scan(name) #define VEC2(type, name1, name2, size) \ std::vector<type> name1(size), name2(size); \ for (int i = 0; i < size; i++) scan(name1[i], name2[i]) #define VEC3(type, name1, name2, name3, size) \ std::vector<type> name1(size), name2(size), name3(size); \ for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i]) #define VEC4(type, name1, name2, name3, name4, size) \ std::vector<type> name1(size), name2(size), name3(size), name4(size); \ for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i], name4[i]) #define VV(type, name, h, w) \ std::vector name((h), std::vector<type>((w))); \ scan(name) // output template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { auto n = v.size(); for (size_t i = 0; i < n; i++) { if (i) os << ' '; os << v[i]; } return os; } template <class... T> void out(const T&... a) { (std::cout << ... << a); } void print() { out('\n'); } template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { out(head); if (sizeof...(Tail)) out(' '); print(tail...); } // for interactive problems void printi() { std::cout << std::endl; } template <class Head, class... Tail> void printi(Head&& head, Tail&&... tail) { out(head); if (sizeof...(Tail)) out(' '); printi(tail...); } // bool output void YES(bool t = 1) { print(t ? "YES" : "NO"); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void NO(bool t = 1) { YES(!t); } void No(bool t = 1) { Yes(!t); } void no(bool t = 1) { yes(!t); } void POSSIBLE(bool t = 1) { print(t ? "POSSIBLE" : "IMPOSSIBLE"); } void Possible(bool t = 1) { print(t ? "Possible" : "Impossible"); } void possible(bool t = 1) { print(t ? "possible" : "impossible"); } void IMPOSSIBLE(bool t = 1) { POSSIBLE(!t); } void Impossible(bool t = 1) { Possible(!t); } void impossible(bool t = 1) { possible(!t); } void FIRST(bool t = 1) { print(t ? "FIRST" : "SECOND"); } void First(bool t = 1) { print(t ? "First" : "Second"); } void first(bool t = 1) { print(t ? "first" : "second"); } void SECOND(bool t = 1) { FIRST(!t); } void Second(bool t = 1) { First(!t); } void second(bool t = 1) { first(!t); } // I/O speed up struct SetUpIO { SetUpIO() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout << std::fixed << std::setprecision(15); } } set_up_io; template <class MS> struct SegmentTree { public: using S = typename MS::S; SegmentTree() : SegmentTree(0) {} SegmentTree(int n) : SegmentTree(std::vector<S>(n, MS::e())) {} SegmentTree(const std::vector<S>& v) : n((int)(v.size())) { log = 0; while ((1U << log) < (unsigned int)(n)) log++; size = 1 << log; d = std::vector<S>(size << 1, MS::e()); for (int i = 0; i < n; i++) d[i + size] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, const S& x) { assert(0 <= p and p < n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } void chset(int p, const S& x) { assert(0 <= p and p < n); p += size; d[p] = MS::op(d[p], x); for (int i = 1; i <= log; i++) update(p >> i); } S operator[](int p) const { assert(0 <= p and p < n); return d[p + size]; } S get(int p) const { assert(0 <= p && p < n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l and l <= r and r <= n); S sml = MS::e(), smr = MS::e(); l += size; r += size; while (l < r) { if (l & 1) sml = MS::op(sml, d[l++]); if (r & 1) smr = MS::op(d[--r], smr); l >>= 1; r >>= 1; } return MS::op(sml, smr); } S all_prod() const { return d[1]; } template <class G> int max_right(int l, G& g) const { assert(0 <= l and l <= n); assert(g(MS::e())); if (l == n) return n; l += size; S sm = MS::e(); do { while ((l & 1) == 0) l >>= 1; if (!g(MS::op(sm, d[l]))) { while (l < size) { l <<= 1; if (g(MS::op(sm, d[l]))) { sm = MS::op(sm, d[l]); l++; } } return l - size; } sm = MS::op(sm, d[l]); l++; } while ((l & -l) != l); return n; } template <class G> int min_left(int r, G& g) const { assert(0 <= r and r <= n); assert(g(MS::e())); if (r == 0) return 0; r += size; S sm = MS::e(); do { r--; while (r > 1 and (r & 1)) r >>= 1; if (!g(MS::op(d[r], sm))) { while (r < size) { r = (r << 1) | 1; if (g(MS::op(d[r], sm))) { sm = MS::op(d[r], sm); r--; } } return r + 1 - size; } sm = MS::op(d[r], sm); } while ((r & -r) != r); return 0; } private: int n, log, size; std::vector<S> d; inline void update(int k) { d[k] = MS::op(d[k << 1], d[(k << 1) | 1]); } }; // MS template <class T> struct MonoidMax { using S = T; static constexpr S op(S a, S b) { return std::max(a, b); } static constexpr S e() { return std::numeric_limits<T>::lowest(); } }; using namespace std; void solve() { I64(N, S, H); VEC3(i64, X, Y, Z, N); vector<i64> cum(N + 1); REP(i, N) cum[i + 1] = cum[i] + Z[i]; // dp[i + 1] = 話 i を聞き終えた時点での得られた知識の最大値 SegmentTree<MonoidMax<i64>> dp(N + 1); dp.set(0, 0); multiset<i64> st; st.insert(-INF<i64>); vector<vector<i64>> event(N + 1); REP(i, N) { // i 番目の話からいくつか連続で聞き始める (配る) // {i}, {i, i+1}, {i, i+1, i+2}, ... とすべて列挙すると間に合わないので // 聞く話の集合のの右端のところまで計算を先送りにする // 先送りにした分の計算 dp.chset(i, *st.rbegin() + cum[i]); // どの話まで聞けるか: 遷移先 (dp[r] の計算までは含めて良い) int r = UB(Y, X[i] + S); // どこから寝る必要があるか: 遷移元 (dp[l] の計算までは含めて良い) int l = UB(Y, X[i] - H); i64 mx = dp.prod(0, l + 1); // max(dp[0], dp[1], ... , dp[l]) st.insert(mx - cum[i]); event[r].push_back(mx - cum[i]); // r = i の場合に備えてここで無効になった先送り分を反映させる FORE(val, event[i]) st.extract(val); } dp.chset(N, *st.rbegin() + cum[N]); // FORE(val, event[N]) st.extract(val); i64 ans = dp.all_prod(); print(ans); return; } int main() { solve(); return 0; }