#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const double PI=acos(-1);
const ll maxn = 1e6+5;
const ll maxm = 3e3+5;
const ll inf = 1ll<<60;
const ll mod = 998244353;
ll pw(ll a, ll p){
ll ret = 1;
while(p > 0){
if (p&1){
ret *= a;
ret %= mod;
}
a *= a;
a %= mod;
p >>= 1;
}
return ret;
}
ll inv(ll a){
return pw(a, mod-2);
}
int n, m;
vector<pip> v;
vector<pip> ina(maxn), inb(maxn);
bool cmp(pip a, pip b){
if (a.f == b.f){
return a.s.f > b.s.f;
}
return a.f < b.f;
}
signed main(){
IOS();
cin>>n>>m;
vector<int> pfa(n+1), pfb(m+1);
REP1(i, n){
cin>>ina[i].f>>ina[i].s.f>>ina[i].s.s;
pfa[i] = pfa[i-1] + ina[i].f;
}
REP1(i, m){
cin>>inb[i].f>>inb[i].s.f>>inb[i].s.s;
pfb[i] = pfb[i-1] + inb[i].f;
}
REP1(i, n){
int dd = upper_bound(ALL(pfb), ina[i].s.f - pfa[i])-pfb.begin()-1;
if (dd >= 0) v.pb({i, {dd, ina[i].s.s}});
}
int jsum = 0;
REP1(i, m){
int dd = upper_bound(ALL(pfa), inb[i].s.f - pfb[i])-pfa.begin()-1;
if (dd >= 0){
jsum += inb[i].s.s;
if (dd < n) v.pb({dd+1, {i-1, -inb[i].s.s}});
}
}
sort(ALL(v), cmp);
/*map<int, int> mp;
mp[0] = 0;
for (auto p:v){
pii ac = p.s;
mp[0] += ac.s;
if (ac.s < 0){
if (ac.f < m) mp[ac.f+1] += -ac.s;
}
else {
auto it = mp.upper_bound(ac.f);
int rem = ac.s;
while (it != mp.end() && (*it).s <= rem){
rem -= (*it).s;
it = mp.erase(it);
}
if (it != mp.end()){
mp[(*it).f] = (*it).s - rem;
}
}
}
int ans = 0;
for (auto v:mp) ans += v.s;
cout<<ans+jsum<<endl;
*/
// testing
vector<int> dp(m+1);
for(auto p:v){
REP1(i, m){
if (i <= p.s.f) dp[i] += p.s.s;
if (i > 0) dp[i] = max(dp[i], dp[i-1]);
}
}
cout<<dp[m]+jsum<<endl;
}
// funny euler tour :)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10032 ms |
63164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
47196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
47196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
47196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
47196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
47196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10032 ms |
63164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10032 ms |
63164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
