제출 #579284

#제출 시각아이디문제언어결과실행 시간메모리
579284lumibonsTwo Dishes (JOI19_dishes)C++17
74 / 100
6755 ms203328 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const ll inf = 1LL << 60; typedef ll sdata; struct operation { ll add = 0, max = -inf; }; sdata combine(sdata dl, sdata dr) { return max(dl, dr); } sdata calculate(operation o, sdata d) { return max(o.max, d + o.add); } operation merge(operation ot, operation ob) { return { ot.add + ob.add, max(ot.max, ob.max + ot.add) }; } const int sn = 1 << 20; sdata s[2 * sn]; operation o[sn]; void apply(int x, operation op) { s[x] = calculate(op, s[x]); if (x < sn) o[x] = merge(op, o[x]); } void push(int x) { apply(x << 1, o[x]); apply(x << 1 | 1, o[x]); o[x] = operation(); } sdata query(int a, int b, int l = 0, int r = sn, int x = 1) { if (b <= l || r <= a) return -inf; if (a <= l && r <= b) return s[x]; push(x); return combine(query(a, b, l, (l + r) / 2, x << 1), query(a, b, (l + r) / 2, r, x << 1 | 1)); } void apply(int a, int b, operation op, int l = 0, int r = sn, int x = 1) { if (b <= l || r <= a) return; if (a <= l && r <= b) return apply(x, op); push(x); apply(a, b, op, l, (l + r) / 2, x << 1); apply(a, b, op, (l + r) / 2, r, x << 1 | 1); s[x] = combine(s[x << 1], s[x << 1 | 1]); } int n[2]; ll a[2][1000100], t[2][1000100], p[2][1000100]; vector<int> rem[1000100]; int main() { cin >> n[0] >> n[1]; for (int j = 0; j < 2; j++) for (int i = 0; i < n[j]; i++) cin >> a[j][i] >> t[j][i] >> p[j][i], i > 0 ? a[j][i] += a[j][i - 1] : 0, t[j][i] -= a[j][i]; ll p1 = 0; for (int i = 0; i < n[1]; i++) if (t[1][i] >= 0) { p1 += p[1][i]; int j = upper_bound(a[0], a[0] + n[0], t[1][i]) - a[0]; rem[j].push_back(i); } apply(0, n[1] + 1, { 0, p1 }); for (int i = 0; i < n[0]; i++) { for (int j : rem[i]) apply(j + 1, n[1] + 1, { 0, query(0, j + 1) }); if (t[0][i] >= 0) { int j = upper_bound(a[1], a[1] + n[1], t[0][i]) - a[1]; apply(j + 1, n[1] + 1, { 0, query(0, j + 1) }); apply(0, j + 1, { p[0][i], -inf }); } for (int j : rem[i]) apply(0, j + 1, { -p[1][j], -inf }); } cout << query(0, n[1] + 1) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...