#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
struct RSQ{
private:
int N;
vector<LL> node;
public:
void init(int n){
N = 1;
while(N < n) N *= 2;
for(int i=0; i<2*N-1; i++) node.PB(0LL);
}
void update(int k, LL x){
k += N-1;
node[k] = x;
while(k > 0){
k = (k-1)/2;
node[k] = node[2*k+1] + node[2*k+2];
}
}
LL sum(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
if(r <= a || b <= l) return 0;
if(a <= l && r <= b) return node[k];
return sum(a, b, 2*k+1, l, (l+r)/2) + sum(a, b, 2*k+2, (l+r)/2, r);
}
void print(){
for(int i=0; i<node.size(); i++) cout << node[i] << " ";
cout << endl;
}
};
int N,M;
LL A[1000000],B[1000000],S[1000000],T[1000000],P[1000000],Q[1000000],yoyuA[1000000],yoyuB[1000000];
vector<pair<LL,LL>> v1,v2; //yoyu,point
RSQ rsq1,rsq2;
map<pair<int,int> , LL> dp;
LL solve(int i, int j, LL nowA, LL nowB, RSQ rsq1, RSQ rsq2){
if(dp.count(MP(i,j)) == 1) return dp[MP(i,j)];
LL ans = 0;
while(i+j < N+M){
//cout << "# " << i << " " << j << endl;
if(j == M){
if(yoyuA[i] >= nowB) ans += P[i];
nowA += S[i];
int idx = lower_bound(v1.begin(), v1.end(), MP(yoyuA[i], P[i])) - v1.begin();
rsq1.update(idx,0);
i++;
continue;
}
if(i == N){
if(yoyuB[j] >= nowA) ans += Q[j];
nowB += T[j];
int idx = lower_bound(v2.begin(), v2.end(), MP(yoyuB[j], Q[j])) - v2.begin();
rsq2.update(idx,0);
j++;
continue;
}
int idx1 = lower_bound(v1.begin(), v1.end(), MP(nowB,LLONG_MIN)) - v1.begin();
int idx2 = lower_bound(v1.begin(), v1.end(), MP(nowB+B[j],LLONG_MIN)) - v1.begin();
LL tmpA = rsq1.sum(idx1, N) - rsq1.sum(idx2, N); //ima toranakya yabai
//cout << idx1 << " " << idx2 << " " << tmpA << endl;
idx1 = lower_bound(v2.begin(), v2.end(), MP(nowA,LLONG_MIN)) - v2.begin();
idx2 = lower_bound(v2.begin(), v2.end(), MP(nowA+A[i],LLONG_MIN)) - v2.begin();
LL tmpB = rsq2.sum(idx1, M) - rsq2.sum(idx2, M);
//cout << idx1 << " " << idx2 << " " << tmpB << endl;
if(tmpA == tmpB){
if(yoyuA[i] >= nowB) ans += P[i];
nowA += A[i];
int idx = lower_bound(v1.begin(), v1.end(), MP(yoyuA[i], P[i])) - v1.begin();
rsq1.update(idx,0);
i++;
LL tmp = ans + solve(i, j, nowA, nowB, rsq1, rsq2);
i--;
rsq1.update(idx,v1[i].second);
nowA -= A[i];
if(yoyuA[i] >= nowB) ans -= P[i];
if(yoyuB[j] >= nowA) ans += Q[j];
nowB += B[j];
idx = lower_bound(v2.begin(), v2.end(), MP(yoyuB[j], Q[j])) - v2.begin();
rsq2.update(idx,0);
j++;
return dp[MP(i,j)] = max(tmp, ans + solve(i, j, nowA, nowB, rsq1, rsq2));
}
else if(tmpA > tmpB){
if(yoyuA[i] >= nowB) ans += P[i];
nowA += A[i];
int idx = lower_bound(v1.begin(), v1.end(), MP(yoyuA[i], P[i])) - v1.begin();
rsq1.update(idx,0);
i++;
continue;
}
else{
if(yoyuB[j] >= nowA) ans += Q[j];
nowB += B[j];
int idx = lower_bound(v2.begin(), v2.end(), MP(yoyuB[j], Q[j])) - v2.begin();
rsq2.update(idx,0);
j++;
continue;
}
}
return dp[MP(i,j)] = ans;
}
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<N; i++) scanf("%lld%lld%lld", A+i, S+i, P+i);
for(int i=0; i<M; i++) scanf("%lld%lld%lld", B+i, T+i, Q+i);
//
LL wa = 0;
for(int i=0; i<N; i++){
wa += A[i];
v1.PB(MP(S[i]-wa, P[i]));
yoyuA[i] = S[i]-wa;
}
sort(v1.begin(), v1.end());
//for(int i=0; i<N; i++) cout << v1[i].first << " " << v1[i].second << endl;
wa = 0;
for(int i=0; i<M; i++){
wa += B[i];
v2.PB(MP(T[i]-wa, Q[i]));
yoyuB[i] = T[i]-wa;
}
sort(v2.begin(), v2.end());
//for(int i=0; i<M; i++) cout << v2[i].first << " " << v2[i].second << endl;
//
rsq1.init(N);
for(int i=0; i<N; i++){
rsq1.update(i, v1[i].second);
}
//rsq1.print();
rsq2.init(M);
for(int i=0; i<M; i++){
rsq2.update(i, v2[i].second);
}
//rsq2.print();
//
cout << solve(0,0,0,0,rsq1,rsq2) << endl;
return 0;
}
Compilation message
dishes.cpp: In member function 'void RSQ::print()':
dishes.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<node.size(); i++) cout << node[i] << " ";
~^~~~~~~~~~~~
dishes.cpp: In function 'int main()':
dishes.cpp:112: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:113:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<N; i++) scanf("%lld%lld%lld", A+i, S+i, P+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:114:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<M; i++) scanf("%lld%lld%lld", B+i, T+i, Q+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4690 ms |
1049600 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 |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4690 ms |
1049600 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 |
4690 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
