Submission #723642

#	Time	Username	Problem	Language	Result	Execution time	Memory
723642		Luicosas	Catfish Farm (IOI22_fish)	C++17	3 / 100	218 ms	61132 KiB

fish

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define ref(x) (*(x))
#define prv(x) for(auto& pval : x) cout << pval << " "; cout << "\n";
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else 
#define debug(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> 
ostream& operator << (ostream& out, vector<T> v) {
    out << "{ ";
    for(auto& i : v) {
        out << i << " ";
    }
    out << "} ";
    return out;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    const int maxh = N + 5;

    vector<vector<array<int,2>>> xpoints(N);
    for(int i = 0; i < M; i++) {
        xpoints[X[i]].pb({Y[i], W[i]});
    }
    for(auto& v : xpoints) {
        sort(itr(v));
    }

    vector<vector<ll>> pfx(N);
    vector<vector<int>> dp_idxs(N);
    for(int x = 0; x < N; x++) {
        if(sz(xpoints[x]) == 0 || xpoints[x][0][0] > 1) {
            pfx[x].pb(0);
            dp_idxs[x].pb(0);
        }
        for(auto& p : xpoints[x]) {
            if(p[0] != 0 && (!sz(dp_idxs[x]) || dp_idxs[x].back() != p[0] - 1)) {
                pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0));
                dp_idxs[x].pb(p[0] - 1);
            }
            if(!sz(dp_idxs[x]) || dp_idxs[x].back() != p[0]) {
                pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0) + p[1]);
                dp_idxs[x].pb(p[0]);
            }
        }
        pfx[x].pb((sz(pfx[x]) ? pfx[x].back() : 0));
        dp_idxs[x].pb(maxh);
    }
    debug(pfx);
    debug(dp_idxs);

    vector<vector<ll>> inc_dp(N), dec_dp(N);
    inc_dp[0].assign(sz(dp_idxs[0]), 0);
    dec_dp[0].assign(sz(dp_idxs[0]), 0);
    for(int x = 1; x < N; x++) {
        int psz = sz(dp_idxs[x - 1]), csz = sz(dp_idxs[x]);

        // calc inc_dp
        inc_dp[x].assign(sz(dp_idxs[x]), 0);
        ll gmx = 0; int gptr = psz - 1;
        for(int i = csz - 1; i >= 0; i--) {
            ll h = dp_idxs[x][i];
            while(gptr >= 0 && dp_idxs[x - 1][gptr] >= h) {
                ll v = max(inc_dp[x - 1][gptr], dec_dp[x - 1][gptr]);
                gmx = max(gmx, v + pfx[x][i]);
                gptr--;
            }
            inc_dp[x][i] = max(inc_dp[x][i], gmx - pfx[x][i]);
        }

        dec_dp[x].assign(csz, 0);
        ll smx = 0; int sptr = 0;
        for(int i = 0; i < csz; i++) {
            ll h = dp_idxs[x][i];
            while(sptr < psz && dp_idxs[x - 1][sptr] < h) {
                ll v = dec_dp[x - 1][sptr];
                smx = max(smx, v - pfx[x - 1][sptr]);
                sptr++;
            }
            dec_dp[x][i] = max(dec_dp[x][i], smx + pfx[x - 1][sptr]);
        }

        if(x == 1) {
            continue;
        }
        int ppsz = sz(dp_idxs[x - 2]);

        int gpptr = ppsz - 1; gptr = psz - 1;
        ll gppmx = 0, gvmx = 0;
        for(int i = csz - 1; i >= 0; i--) {
            ll h = dp_idxs[x][i];
            while(gptr >= 0 && dp_idxs[x - 1][gptr] >= h) {
                while(gpptr >= 0 && dp_idxs[x - 2][gpptr] >= dp_idxs[x - 1][gptr]) {
                    gppmx = max(gppmx, dec_dp[x - 2][gpptr]);
                    gppmx = max(gppmx, inc_dp[x - 2][gpptr]);
                    gpptr--;
                }
                gvmx = max(gvmx, pfx[x - 1][gptr] + gppmx);
                gptr--;
            }
            dec_dp[x][i] = max(dec_dp[x][i], gvmx);
        }

        
    }
    debug(inc_dp);
    debug(dec_dp);
    
    ll ans = 0;
    for(auto& p : inc_dp[N - 1]) {
        ans = max(ans, p);
    }
    for(auto& p : dec_dp[N - 1]) {
        ans = max(ans, p);
    }
    return ans;
}

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