Submission #789973

#TimeUsernameProblemLanguageResultExecution timeMemory
789973someoneTwo Dishes (JOI19_dishes)C++14
3 / 100
1 ms468 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct Point { int x, y, val; }; const int M = 1 << 4, N = 2 * M, T = 20, INF = 1e18 + 42; int maxi[N], tag[N]; void applyOp(int i, int add) { tag[i] += add; maxi[i] += add; } void propage(int i) { applyOp(i*2, tag[i]); applyOp(i*2+1, tag[i]); tag[i] = 0; } int update(int i, int deb, int fin, int l, int r, int add) { if(r <= deb || fin <= l) return -2*INF; if(l <= deb && fin <= r) { applyOp(i, add); return maxi[i]; } propage(i); int mid = ((deb + fin) >> 1), ans = max(update(i*2, deb, mid, l, r, add), update(i*2+1, mid, fin, l, r, add)); maxi[i] = max(maxi[i*2], maxi[i*2+1]); return ans; } vector<int> lig[M]; vector<Point> point; int score = 0, ans = 0, sz[2], value[N], a[2][M], t[2][M], pt[2][M], pos[2][M], dp[T][T]; void solve() { score = ans = 0; point.clear(); for(int i = 0; i < M; i++) lig[i].clear(); for(int i = 0; i < N; i++) tag[i] = 0, maxi[i] = -INF, value[i] = -INF; update(1, 0, M, sz[0], sz[0]+1, INF); for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) a[i][j] += a[i][j-1]; a[0][sz[0]+1] = a[1][sz[1]+1] = INF; /* for(int i = 0; i <= sz[0]; i++) for(int j = 0; j <= sz[1]; j++) dp[i][j] = -INF; dp[0][0] = 0; for(int i = 0; i <= sz[0]; i++) for(int j = 0; j <= sz[1]; j++) { if(a[0][i+1] + a[1][j] <= t[0][i+1]) { dp[i+1][j] = max(dp[i+1][j], dp[i][j] + pt[0][i+1]); } else { dp[i+1][j] = max(dp[i+1][j], dp[i][j]); } if(a[0][i] + a[1][j+1] <= t[1][j+1]) { dp[i][j+1] = max(dp[i][j+1], dp[i][j] + pt[1][j+1]); } else { dp[i][j+1] = max(dp[i][j+1], dp[i][j]); } }*/ for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) pos[i][j] = (int)(upper_bound(a[1-i], a[1-i] + sz[1-i] + 1, t[i][j] - a[i][j]) - a[1-i]) - 1; for(int j = 0; j <= sz[0]; j++) if(pos[0][j] != -1) point.push_back({j, pos[0][j], pt[0][j]}); for(int j = 1; j <= sz[1]; j++) { if(pos[1][j] != -1) { score += pt[1][j]; if(pos[1][j] != sz[0]) point.push_back({pos[1][j]+1, j-1, -pt[1][j]}); } } for(int i = 0; i < (int)point.size(); i++) lig[point[i].x].push_back(i); point.push_back({sz[0], sz[1], 0}); sort(point.begin(), point.end(), [](Point p1, Point p2) { if(p1.x == p2.x) return p1.y < p2.y; return p1.x > p2.x; }); for(int i = 1; i < (int)point.size(); i++) if(point[i].x == point[i-1].x && point[i].y == point[i-1].y) { point[i-1].x = point[i-1].y = -1; point[i].val += point[i-1].val; point[i-1].val = 0; } for(int i = 0; i < (int)point.size(); i++) { if(point[i].x != -1) { for(int j = 0; j < i; j++) { if(point[j].y >= point[i].y) { int c = value[j]; for(int k = j; k < i; k++) if(point[k].y >= point[j].y) c += point[k].val; value[i] = max(value[i], c); } } if(point[i].x == sz[0]) value[i] = 0; if(point[i].x == 0 && point[i].y == 0) ans = value[i]; //cout << value[i] << ' '; } } //cout << '\n'; //cout << ans + score << '\n'; /* for(int x = sz[0]; x >= 0; x--) { for(int id : lig[x]) { Point p = point[id]; value[id] = update(1, 0, M, p.y, sz[0]+1, 0); if(p.x == 0 && p.y == 0) ans = value[id]; } for(int id : lig[x]) { Point p = point[id]; int pre = update(1, 0, M, p.y, p.y+1, 0); update(1, 0, M, p.y, p.y+1, value[id] - pre); } for(int id : lig[x]) { Point p = point[id]; update(1, 0, M, 0, p.y+1, p.val); } for(int i = 0; i <= sz[0]; i++) cout << update(1, 0, M, i, i+1, 0) << ' '; cout << '\n' << '\n'; }*/ /* cout << '\n'; cout << ans << ' ' << score << '\n';*/ cout << ans + score << '\n'; //cout << dp[sz[0]][sz[1]] << '\n'; /* if(dp[sz[0]][sz[1]] != ans + score) { cout << "Differ\n"; for(Point p : point) cout << p.x << ' ' << p.y << ' ' << p.val << '\n'; cout << '\n'; for(int i = 0; i < 2; i++) { for(int j = 1; j <= sz[i]; j++) cout << pos[i][j] << ' '; cout << '\n'; } cout << '\n'; cout << ans << ' ' << score << '\n'; cout << dp[sz[0]][sz[1]] << ' ' << ans + score << '\n'; cout << sz[0] << ' ' << sz[1] << '\n'; for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) cout << a[i][j] << ' ' << t[i][j] << ' ' << pt[i][j] << '\n'; cout << '\n' << '\n'; }*/ } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> sz[0] >> sz[1]; for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) cin >> a[i][j] >> t[i][j] >> pt[i][j]; solve();/* for(int x = 0; x < 100000; x++) { srand(time(0) + x); sz[0] = sz[1] = 10; for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) { a[i][j] = (rand() % 10) + 1; t[i][j] = (rand() % 20) + 1; pt[i][j] = (rand() % 2000000000) - 1000000000; } solve(); }*/ }
#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...