Submission #1159587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159587		Math4Life2020	메기 농장 (IOI22_fish)	C++20	100 / 100	927 ms	289280 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 1e5+5; const ll INF = 1e18;
vector<pii> vctf[Nm];
map<ll,ll> psw[Nm]; //current x, lower bound at y0 -> sum of ws with y>=y0
vector<ll> yc[Nm]; //ys to consider
gp_hash_table<ll,ll> dp1[Nm];
gp_hash_table<ll,ll> dp2[Nm];
gp_hash_table<ll,ll> dp3[Nm];
//dp1: ...,a,0; store a
//dp2: ...,a,b; a<=b; store b
//dp3: ...,a,b; a>=b; store b

ll getps(ll xc, ll v) {
    auto A0 = *(psw[xc].lower_bound(v));
    return A0.second;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for (ll i=0;i<M;i++) {
        vctf[X[i]].push_back({Y[i],W[i]});
    }
    for (ll i=0;i<Nm;i++) {
        sort(vctf[i].begin(),vctf[i].end());
        psw[i][INF]=0;
        ll swcur = 0;
        for (ll T=(vctf[i].size()-1);T>=0;T--) {
            swcur += vctf[i][T].second;
            psw[i][vctf[i][T].first]=swcur;
        }
    }
    for (ll i=0;i<N;i++) {
        set<ll> scur;
        if (i>0) {
            for (pii p0: vctf[i-1]) {
                scur.insert(p0.first);
            }
        }
        if (i<(N-1)) {
            for (pii p0: vctf[i+1]) {
                scur.insert(p0.first);
            }
        }
        yc[i].push_back(0);
        for (ll x0: scur) {
            if (x0>=0) {
                yc[i].push_back(x0+1);
            }
        }
    }
    //DP: # of terms active -> value at <=(current x) SO FAR
    //dp1: ...,a,0; store a
    //dp2: ...,a,b; a<=b; store b
    //dp3: ...,a,b; a>=b; store b; MUST go down
    dp1[0][0]=0;
    for (ll i=0;i<N;i++) {
        //dp1 -> dp1
        for (pii p0: dp1[i]) {
            dp1[i+1][0]=max(dp1[i+1][0],p0.second);
        }
        //dp1 -> dp2
        ll PMAX1 = -INF;
        for (pii p0: dp1[i]) {
            PMAX1 = max(PMAX1,p0.second);
        }
        for (ll yv: yc[i]) {
            dp2[i+1][yv]=max(dp2[i+1][yv],PMAX1);
        }
        if (i>0) {
            vector<pii> dp1v;
            for (pii p0: dp1[i]) {
                dp1v.push_back(p0);
            }
            sort(dp1v.begin(),dp1v.end());
            vector<pii> vt1;
            vt1.push_back({-INF,-INF});
            ll cmax = -INF;
            for (pii p0: dp1v) {
                ll vcur = p0.second+getps(i-1,p0.first);
                if (vcur > cmax) {
                    cmax = vcur;
                    vt1.push_back({p0.first,vcur});
                }
            }
            for (ll yv: yc[i]) {
                auto A0 = *(--lower_bound(vt1.begin(),vt1.end(),(pii){(ll)yc,(ll)INF}));
                dp2[i+1][yv]=max(dp2[i+1][yv],(A0).second-getps(i-1,yv));
            }
        }
        //dp2 -> dp1
        for (pii p0: dp2[i]) {
            dp1[i+1][p0.first]=max(dp1[i+1][p0.first],p0.second+getps(i,0)-getps(i,p0.first));
        }
        //dp2 -> dp2
        vector<pii> vt1;
        vector<pii> dp2v;
        for (pii p0: dp2[i]) {
            dp2v.push_back(p0);
        }
        sort(dp2v.begin(),dp2v.end());
        vt1.push_back({-INF,-INF});
        ll cmax = -INF;
        for (pii p0: dp2v) {
            ll vcur = p0.second+getps(i-1,p0.first);
            if (vcur > cmax) {
                cmax = vcur;
                vt1.push_back({p0.first,vcur});
            }
        }
        for (ll yv: yc[i]) {
            auto A0 = *(--lower_bound(vt1.begin(),vt1.end(),(pii){(ll)yc,(ll)INF}));
            dp2[i+1][yv]=max(dp2[i+1][yv],(A0).second-getps(i-1,yv));
        }
        //dp2 -> dp3
        vector<pii> vt4I,vt4;
        for (pii p0: dp2[i]) {
            vt4I.push_back({p0.first,p0.second-getps(i,p0.first)});
        }
        sort(vt4I.rbegin(),vt4I.rend());
        ll cmaxv0 = -INF;
        for (pii p0: vt4I) {
            if (p0.second>cmaxv0) {
                cmaxv0 = p0.second;
                vt4.push_back(p0);
            }
        }
        vt4.push_back({INF,-INF});
        sort(vt4.begin(),vt4.end());
        for (ll yv: yc[i]) {
            pii p0 = *lower_bound(vt4.begin(),vt4.end(),(pii){yv,-INF});
            dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv));
        }  

        //dp3 -> dp1
        for (pii p0: dp3[i]) {
            dp1[i+1][p0.first]=max(dp1[i+1][p0.first],p0.second+getps(i,0)-getps(i,p0.first));
        }
        //dp3 -> dp3
        vector<pii> vt5I,vt5;
        for (pii p0: dp3[i]) {
            vt5I.push_back({p0.first,p0.second-getps(i,p0.first)});
        }
        sort(vt5I.rbegin(),vt5I.rend());
        ll cmaxv = -INF;
        for (pii p0: vt5I) {
            if (p0.second>cmaxv) {
                cmaxv = p0.second;
                vt5.push_back(p0);
            }
        }
        vt5.push_back({INF,-INF});
        sort(vt5.begin(),vt5.end());
        for (ll yv: yc[i]) {
            pii p0 = *lower_bound(vt5.begin(),vt5.end(),(pii){yv,-INF});
            dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv));
        }  
        // cout << "print states after reading column i="<<i<<"\n";
        // cout << "dp1:\n";
        // for (pii p0: dp1[i+1]) {
        //     cout << p0.first << ": " <<p0.second<<"\n";
        // }
        // cout << "dp2:\n";
        // for (pii p0: dp2[i+1]) {
        //     cout << p0.first << ": " <<p0.second<<"\n";
        // }
        // cout << "dp3:\n";
        // for (pii p0: dp3[i+1]) {
        //     cout << p0.first << ": " <<p0.second<<"\n";
        // }
    }
    ll ans = 0;
    for (pii p0: dp1[N]) {
        ans = max(ans,p0.second);
    }
    for (pii p0: dp2[N]) {
        ans = max(ans,p0.second);
    }
    for (pii p0: dp3[N]) {
        ans = max(ans,p0.second);
    }
    return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16