#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
class SegmentTree {
private:
// We keep dp[n] = tree[n] + transition[n], to be able to do updates quickly
int sz;
vector<lint> tree;
vector<lint> lazy_sum;
vector<lint> lazy_max;
vector<lint> transition;
void Push(int n) {
for (int c = 0; c < 2; c++) {
tree[n * 2 + c] += lazy_sum[n];
lazy_sum[n * 2 + c] += lazy_sum[n];
lazy_max[n * 2 + c] += lazy_sum[n];
tree[n * 2 + c] = max(tree[n * 2 + c], lazy_max[n]);
lazy_max[n * 2 + c] = max(lazy_max[n * 2 + c], lazy_max[n]);
}
lazy_max[n] = -INF;
lazy_sum[n] = 0;
}
void RangeSumUpdate(int n, int tl, int tr, int l, int r, lint x, bool update_tree) {
if (r < tl || tr < l || tl > tr || l > r) return;
if (l <= tl && tr <= r) {
if (update_tree) {
tree[n] += x;
lazy_sum[n] += x;
lazy_max[n] += x;
} else {
transition[n] += x;
}
return;
}
Push(n);
int mid = (tl + tr) / 2;
RangeSumUpdate(n * 2, tl, mid, l, r, x, update_tree);
RangeSumUpdate(n * 2 + 1, mid + 1, tr, l, r, x, update_tree);
}
void RangeMaximumUpdate(int n, int tl, int tr, int l, int r, lint x) {
if (r < tl || tr < l || tl > tr || l > r) return;
if (l <= tl && tr <= r) {
tree[n] = max(tree[n], x);
lazy_max[n] = max(lazy_max[n], x);
return;
}
Push(n);
int mid = (tl + tr) / 2;
RangeMaximumUpdate(n * 2, tl, mid, l, r, x);
RangeMaximumUpdate(n * 2 + 1, mid + 1, tr, l, r, x);
}
lint QueryTree(int n, int tl, int tr, int pos) {
if (tl == tr) return tree[n]; // dp[] = tree[] + transition[]
Push(n);
int mid = (tl + tr) / 2;
if (pos <= mid) {
return QueryTree(n * 2, tl, mid, pos);
} else {
return QueryTree(n * 2 + 1, mid + 1, tr, pos);
}
}
lint Query(int n, int tl, int tr, int pos) {
if (tl == tr) return tree[n] + transition[n]; // dp[] = tree[] + transition[]
Push(n);
int mid = (tl + tr) / 2;
if (pos <= mid) {
return transition[n] + Query(n * 2, tl, mid, pos);
} else {
return transition[n] + Query(n * 2 + 1, mid + 1, tr, pos);
}
}
public:
SegmentTree(int n) : sz(n) {
tree.assign(4 * sz, 0);
lazy_sum.assign(4 * sz, 0);
lazy_max.assign(4 * sz, -INF);
transition.assign(4 * sz, 0);
}
void UpdateSumTree(int l, int r, lint x) { // range sum update on dp
return RangeSumUpdate(1, 0, sz - 1, l, r, x, true);
}
void UpdateTransition(int l, int r, lint x) { // range sum update on transition
return RangeSumUpdate(1, 0, sz - 1, l, r, x, false);
}
void UpdateMaximumTree(int l, int r, lint x) { // dp[k] = max(dp[k], transition[k] + x), x = dp[0], for all nodes
return RangeMaximumUpdate(1, 0, sz - 1, l, r, x);
}
lint QueryTree(int pos) {
return QueryTree(1, 0, sz - 1, pos);
}
lint Query(int pos) {
return Query(1, 0, sz - 1, pos);
}
};
int N, M;
vector<int> X; // X[i] = maximum index j, such that A[1] + A[2] + ... + A[i] + B[1] + B[2] + ... + B[j] <= S[i]
vector<int> Y; // Y[j] = maximum index i, such that A[1] + A[2] + ... + A[i] + B[1] + B[2] + ... + B[j] <= T[j]
vector<int> P;
vector<int> Q;
lint NaiveDP(bool dbg = false) {
vector<vector<lint>> dp(N + 1, vector<lint>(M + 1, -INF));
dp[0][0] = 0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= M; j++) {
if (j < M) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + (i <= Y[j + 1] ? Q[j + 1] : 0));
if (i < N) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (j <= X[i + 1] ? P[i + 1] : 0));
}
}
if (dbg) {
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= M; j++) {
cout << dp[i][j] << " \n"[j == M];
}
}
}
return dp[N][M];
}
lint SegmentTreeDP() {
SegmentTree seg(M + 1);
vector<vector<int>> deactivate(N + 2); // deactivate Q[j] at row i
for (int j = 1; j <= M; j++) {
if (0 <= Y[j]) {
seg.UpdateTransition(j, M, Q[j]);
deactivate[Y[j]].emplace_back(j);
}
}
for (int i = 0; i <= N; i++) {
seg.UpdateSumTree(0, X[i], P[i]);
seg.UpdateMaximumTree(X[i] + 1, M, seg.QueryTree(X[i])); // maintain monotonicity
sort(begin(deactivate[i]), end(deactivate[i]));
for (auto &j : deactivate[i]) {
seg.UpdateTransition(j, M, -Q[j]);
seg.UpdateSumTree(j, M, Q[j]);
// make tree[] monotone again, by range maximum update on tree.
// This simulates the transition dp[i][j + 1] from dp[i][j]
// As only the values [j + 1, M] changes, we only need to compare
// it with the value at [j].
seg.UpdateMaximumTree(j, M, seg.QueryTree(j - 1));
}
// for (int j = 0; j <= M; j++) {
// cout << seg.Query(j) << " \n"[j == M];
// }
}
return seg.Query(M);
}
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
void Read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> M;
// N = 10, M = 10;
vector<int> A(N + 1), B(M + 1);
vector<lint> S(N + 1), T(M + 1);
P.resize(N + 1), Q.resize(M + 1);
X.resize(N + 1), Y.resize(M + 1);
for (int i = 1; i <= N; i++) {
// A[i] = rnd() % 100;
// S[i] = rnd() % 1000;
// P[i] = rnd() % 100;
cin >> A[i] >> S[i] >> P[i];
A[i] += A[i - 1];
}
for (int i = 1; i <= M; i++) {
// B[i] = rnd() % 100;
// T[i] = rnd() % 1000;
// Q[i] = rnd() % 100;
cin >> B[i] >> T[i] >> Q[i];
B[i] += B[i - 1];
}
for (int i = 0; i <= N; i++) {
X[i] = upper_bound(begin(B), end(B), S[i] - A[i]) - begin(B) - 1;
}
for (int i = 0; i <= M; i++) {
Y[i] = upper_bound(begin(A), end(A), T[i] - B[i]) - begin(A) - 1;
}
}
int main() {
Read();
cout << NaiveDP() << "\n";
// cout << SegmentTreeDP() << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
991 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
991 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
991 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
