#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Point {
int x, y, val;
};
const int M = 1 << 20, N = 2 * M, T = 12, 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);
/*
for(Point p : point)
cout << p.x << ' ' << p.y << ' ' << p.val << '\n';
cout << '\n' << '\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';
/*
if(dp[sz[0]][sz[1]] != ans + score) {
cout << "Differ\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';
}*/
}
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 < 1000; 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() % 100) + 1;
pt[i][j] = (rand() % 20) - 10;
}
solve();
}*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10094 ms |
100492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
74236 KB |
Output is correct |
| 2 |
Correct |
32 ms |
74208 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
74188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
74236 KB |
Output is correct |
| 2 |
Correct |
32 ms |
74208 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
74188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
74236 KB |
Output is correct |
| 2 |
Correct |
32 ms |
74208 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
74188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
74236 KB |
Output is correct |
| 2 |
Correct |
32 ms |
74208 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
74188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
74236 KB |
Output is correct |
| 2 |
Correct |
32 ms |
74208 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
74188 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10094 ms |
100492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10094 ms |
100492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
