#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7, inf = 1e18; // !
int lazy[4 * N][2], a[N][2], c[N][2], s[N][2], n[2];
vector<pii> x[N];
pii t[4 * N];
pii merge(pii x, pii y) {
return (x.f < y.f ? y : x);
}
void push(int u, int l, int r) {
if(lazy[u][0] != -inf) {
t[u].f = lazy[u][0];
if(l < r) {
lazy[2 * u][1] = lazy[2 * u + 1][1] = 0;
lazy[2 * u][0] = lazy[2 * u + 1][0] = lazy[u][0];
}
lazy[u][0] = -inf;
}
if(lazy[u][1] != 0) {
t[u].f += lazy[u][1];
if(l < r) {
lazy[2 * u][1] += lazy[u][1];
lazy[2 * u + 1][1] += lazy[u][1];
}
lazy[u][1] = 0;
}
}
void upd(int u, int st, int en, int l, int r, int x, int T) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u][T] = x;
push(u, l, r);
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, x, T); upd(2 * u + 1, st, en, mid + 1, r, x, T);
t[u] = merge(t[2 * u], t[2 * u + 1]);
}
pii get(int u, int st, int en, int l, int r) {
push(u, l, r);
if(l > en || r < st) return {-inf, 0};
if(st <= l && r <= en) return t[u];
int mid = (l + r) / 2;
return merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
void build(int u, int l, int r) {
t[u].s = l; lazy[u][0] = -inf;
if(l == r) return;
build(2 * u, l, (l + r) / 2); build(2 * u + 1, (l + r)/ 2 + 1, r);
}
main(){
int m;
cin >> n[0] >> n[1];
for(int t = 0; t < 2; t++) {
for(int i = 1; i <= n[t]; i++) {
cin >> a[i][t] >> s[i][t] >> c[i][t];
a[i][t] += a[i - 1][t];
}
}
int ans = 0;
for(int t = 0; t < 2; t++) {
int R = n[t^1];
for(int i = 1; i <= n[t]; i++) {
int l = 0, r = n[t^1], R = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(a[i][t] + a[mid][t^1] <= s[i][t]) R = mid, l = mid + 1;
else r = mid - 1;
}
if(!t) {
// R tu aris i - s win mashin ver vigebt
++R;
ans += c[i][t];
//cout << i << " __ " << R << " " << a[i][t] << endl;
x[i].push_back({R, -c[i][t]});
continue;
}
++R;
if(R == n[0] + 1) {
ans += c[i][t];
continue;
}
// R tu aris i - s shemdeg mashin vigebt
// i tu aris R - is win mashin vigebt
x[R].push_back({i, c[i][t]});
}
}
/*
vector<int> dp(n[1] + 1);
for(int i = 1; i <= n[0]; i++) {
for(int j = 1; j <= n[1]; j++) dp[j] = max(dp[j], dp[j - 1]);
sort(x[i].begin(), x[i].end());
for(int k = 0; k < x[i].size(); k++) {
for(int j = x[i][k].f; j <= n[1]; j++) dp[j] += x[i][k].s;
}
}
int mn = -inf;
for(int i = 0; i <= n[1]; i++) mn = max(mn, dp[i]);
cout << ans + mn << "\n";
return 0; */
build(1, 0, n[1]);
for(int i = 1; i <= n[0]; i++) {
sort(x[i].begin(), x[i].end());
int R = n[1], f = 0;
// prefix max
while(R >= 0) {
pii X = get(1, 1, R, 0, n[1]);
upd(1, X.s, R, 0, n[1], X.f, 0);
R = X.s - 1;
++f;
assert(f - 2 <= x[i - 1].size());
}
int c = 0;
for(int j = 0; j < x[i].size(); j++) {
c = x[i][j].s;
upd(1, x[i][j].f, n[1], 0, n[1], c, 1);
}
}
cout << t[1].f + ans;
}
Compilation message
dishes.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
56 | main(){
| ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:67:13: warning: unused variable 'R' [-Wunused-variable]
67 | int R = n[t^1];
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from dishes.cpp:1:
dishes.cpp:121:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | assert(f - 2 <= x[i - 1].size());
| ^
dishes.cpp:125:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int j = 0; j < x[i].size(); j++) {
| ~~^~~~~~~~~~~~~
dishes.cpp:57:10: warning: unused variable 'm' [-Wunused-variable]
57 | int m;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
569 ms |
84768 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
569 ms |
84768 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
569 ms |
84768 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
