Submission #995173

#	Time	Username	Problem	Language	Result	Execution time	Memory
995173		browntoad	Two Dishes (JOI19_dishes)	C++14	0 / 100	10032 ms	63164 KiB

dishes

#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 :)

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9