#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXT = 2100000;
const int mod = 1e9 + 7;
using lint = long long;
using pi = pair<int, int>;
struct pnt{
int x, y;
lint c;
bool operator<(const pnt &p)const{
return pi(x, y) < pi(p.x, p.y);
}
};
struct seg{
lint lazy[MAXT], tree[MAXT];
void lazydown(int p){
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
tree[2*p] += lazy[p];
tree[2*p+1] += lazy[p];
lazy[p] = 0;
tree[2*p] = max(tree[2*p], tree[p]);
tree[2*p+1] = max(tree[2*p+1], tree[p]);
tree[p] = 0;
}
void add(int s, int e, int ps, int pe, int p, lint v){
if(e < ps || pe < s) return;
if(s <= ps && pe <= e){
lazy[p] += v;
tree[p] += v;
return;
}
int pm = (ps + pe) / 2;
lazydown(p);
add(s, e, ps, pm, 2*p, v);
add(s, e, pm + 1, pe, 2*p + 1, v);
}
void upperize(int s, int e, int ps, int pe, int p, lint v){
if(e < ps || pe < s) return;
if(s <= ps && pe <= e){
tree[p] = max(tree[p], v);
return;
}
int pm = (ps + pe) / 2;
lazydown(p);
upperize(s, e, ps, pm, 2*p, v);
upperize(s, e, pm+1, pe, 2*p+1, v);
}
lint query(int pos, int s, int e, int p){
if(s == e) return tree[p];
int m = (s + e) / 2;
lazydown(p);
if(pos <= m) return query(pos, s, m, 2*p);
return query(pos, m+1, e, 2*p+1);
}
}seg;
int n, m;
lint a[MAXN], s[MAXN], p[MAXN];
lint b[MAXN], t[MAXN], q[MAXN];
int da[MAXN], db[MAXN];
lint dp[MAXN];
vector<pnt> v, w;
lint getCostV(int s, int e, int x){
lint ret = 0;
for(auto &i : v){
if(s <= i.x && i.x <= e && i.y >= x) ret += i.c;
}
return ret;
}
lint getCostW(int s, int e, int x){
lint ret = 0;
for(auto &i : w){
if(s <= i.x && i.x <= e && i.y <= x) ret += i.c;
}
return ret;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
a[i] += a[i-1];
}
for(int i=1; i<=m; i++){
scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
b[i] += b[i-1];
}
lint ret = 0;
v.push_back({0, 0, 0});
for(int i=1; i<=n; i++){
da[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b;
if(da[i] > 0){
if(p[i] > 0) v.push_back({i, da[i], p[i]});
else w.push_back({i, da[i], -p[i]}), ret += p[i];
}
}
for(int i=1; i<=m; i++){
db[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a;
if(db[i] > 0){
if(q[i] > 0) w.push_back({db[i], i, q[i]});
else v.push_back({db[i], i, -q[i]}), ret += q[i];
}
}
sort(v.begin(), v.end());
sort(w.begin(), w.end());
v.push_back({n + 1, m + 1, 0});
int pw = 0;
lint tree[MAXT] = {};
for(int i=1; i<v.size(); i++){
dp[i] = -1e18;
for(int j=0; j<i; j++){
if(v[j].y <= v[i].y){
dp[i] = max(dp[i], dp[j]
+ getCostV(v[j].x + 1, v[i].x, v[j].y + 1)
+ getCostW(v[j].x + 1, v[i].x, v[j].y));
}
}
/*
for(int j=v[i].y; j<=m+1; j++) tree[j] += v[i].c;
//M0; j<=v[i].y; j++) tree[j] += v[i].c;
//seg.add(0, v[i].y, 0, m + 1, 1, v[i].c);
while(pw < w.size() && pi(w[pw].x, w[pw].y) <= pi(v[i].x, v[i].y)){
for(int j=0; j<w[pw].y; j++) tree[j] += w[pw].c;
// seg.add(w[pw].y + 1, m + 1, 0, m + 1, 1, w[pw].c);
pw++;
}
lint val = tree[v[i].y]; // seg.query(v[i].y, 0, m + 1, 1);
for(int j=v[i].y; j<=m+1; j++) tree[j] = max(tree[j], val);
//seg.upperize(v[i].y, m + 1, 0, m + 1, 1, val);
}
lint dap = -1e18;
for(int i=0; i<m+2; i++) dap = max(dap, tree[i]);//seg.query(i, 0, m + 1, 1));
*/
}
lint dap = dp[v.size() - 1];
cout << ret + dap << endl;
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:115:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<v.size(); i++){
~^~~~~~~~~
dishes.cpp:113:6: warning: unused variable 'pw' [-Wunused-variable]
int pw = 0;
^~
dishes.cpp:114:7: warning: unused variable 'tree' [-Wunused-variable]
lint tree[MAXT] = {};
^~~~
dishes.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
dishes.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10085 ms |
20136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10085 ms |
20136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
10085 ms |
20136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
