Submission #723680

#	Time	Username	Problem	Language	Result	Execution time	Memory
723680		Luicosas	Catfish Farm (IOI22_fish)	C++17	100 / 100	307 ms	67296 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 ll maxh = N + 5;

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

    vector<vector<ll>> pfx(N);
    vector<vector<ll>> dp_idxs(N);
    for(ll 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(ll x = 1; x < N; x++) {
        ll 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; ll gptr = psz - 1;
        for(ll 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; ll sptr = 0;
        for(ll 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 - 1]);
        }

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

        ll gpptr = ppsz - 1; gptr = psz - 1;
        ll gppmx = 0, gvmx = 0;
        for(ll 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);
        }

        ll spptr = 0; sptr = 0;
        ll sppmx = 0;
        for(ll i = 0; i < csz; i++) {
            ll h = dp_idxs[x][i];
            while(spptr < ppsz && dp_idxs[x - 2][spptr] <= h) {
                sppmx = max(sppmx, dec_dp[x - 2][spptr]);
                sppmx = max(sppmx, inc_dp[x - 2][spptr]);
                spptr++;
            }
            while(sptr + 1 < psz && dp_idxs[x - 1][sptr + 1] <= h) {
                sptr++;
            }
            dec_dp[x][i] = max(dec_dp[x][i], sppmx + pfx[x - 1][sptr]);
        }
    }
    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: 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