Submission #361275

#TimeUsernameProblemLanguageResultExecution timeMemory
361275Lam_lai_cuoc_doi코알라 (JOI13_koala)C++17
100 / 100
118 ms37484 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; const bool typetest = 0; const ll Inf = 2e18; const int N = 1e5 + 5; struct Trie { ll v; Trie *child[2]; Trie() { v = -Inf; child[0] = child[1] = NULL; } } beg; ll k, m, d, a, b[N], dp[N]; int n; ll t[N]; void Read() { cin >> k >> m >> d >> a >> n; for (int i = 1; i <= n; ++i) cin >> t[i] >> b[i]; t[0] = k; t[n + 1] = m; } #define bit(i, x) (((x) >> (i)) & 1) void Add(Trie *a, int x, ll v) { int id = 30; while (1) { if (id == -1) { a->v = max(a->v, v); return; } if (!(a->child[bit(id, x)])) a->child[bit(id, x)] = new Trie; a->v = max(a->v, v); a = a->child[bit(id, x)]; --id; } } ll Get_up(Trie *a, int x) { int id = 30; ll ans(-Inf); while (1) { if (id == -1) { ans = max(ans, a->v); break; } if (bit(id, x)) { if (a->child[1]) a = a->child[1]; else break; } else { if (a->child[1]) ans = max(ans, a->child[1]->v); if (a->child[0]) a = a->child[0]; else break; } --id; } return ans; } ll Get_down(Trie *a, int x) { int id = 30; ll ans(-Inf); while (1) { if (id == -1) { ans = max(ans, a->v); break; } if (!bit(id, x)) { if (a->child[0]) a = a->child[0]; else break; } else { if (a->child[0]) ans = max(ans, a->child[0]->v); if (a->child[1]) a = a->child[1]; else break; } --id; } return ans; } void Solve() { Add(&beg, t[0] % d, t[0] / d * a); for (int i = 1; i <= n + 1; ++i) { dp[i] = Get_up(&beg, t[i] % d) - t[i] / d * a; if (t[i] % d > 0) dp[i] = max(dp[i], Get_down(&beg, t[i] % d - 1) - t[i] / d * a - a); dp[i] += b[i]; Add(&beg, t[i] % d, dp[i] + t[i] / d * a); } cout << dp[n + 1]; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t(1); if (typetest) cin >> t; for (int _ = 1; _ <= t; ++_) { Read(); Solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...