Submission #1158751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158751		InvMOD	Catfish Farm (IOI22_fish)	C++20	100 / 100	228 ms	87104 KiB

fish

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "fish.h"
#endif // name

using namespace std;

#define fi first
#define se second

//#define int long long
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define dbg(x) "[" << #x " = " << (x) << "]"

using ll = long long;

namespace Subtask1{
    bool ckSub(vector<int>& X){
        for(int i = 0; i < sz(X); i++){
            if(X[i] & 1) return false;
        }
        return true;
    }

    ll process(vector<int>& W){
        ll answer = 0;
        for(int i = 0; i < sz(W); i++){
            answer += W[i];
        }
        return answer;
    }
}

namespace Subtask2{
    bool ckSub(vector<int>& X){
        for(int i = 0; i < sz(X); i++){
            if(X[i] > 1) return false;
        }
        return true;
    }

    ll process(int n, vector<int>& X, vector<int>& Y, vector<int>& W){
        vector<vector<int>> row(2, vector<int>(n + 1));

        vector<ll> sum(2, 0);
        for(int i = 0; i < sz(X); i++){
            row[X[i]][Y[i] + 1] = W[i];
            sum[X[i]] += 1ll * W[i];
        }

        ll answer = max(sum[0], sum[1]), pref = 0;
        if(n > 2){
            for(int i = 1; i <= n; i++){
                pref += row[0][i];
                sum[1] -= row[1][i];

                answer = max(answer, pref + sum[1]);
            }
        }
        return answer;
    }
}

namespace Subtask45{
    bool ckSub(int n){
        return n <= 300;
    }

    ll process(int n, vector<int>& X, vector<int>& Y, vector<int>& W){
        vector<vector<int>> row(n + 1, vector<int>(n + 1));

        for(int i = 0; i < sz(X); i++){
            row[X[i] + 1][Y[i] + 1] = W[i];
        }

        vector<vector<ll>> pref(n + 1, vector<ll>(n + 1));

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                pref[i][j] = pref[i][j - 1] + row[i][j];
            }
        }

        vector<vector<ll>> f(n + 1, vector<ll>(n + 1));
        vector<vector<ll>> g(n + 1, vector<ll>(n + 1));

        // f[i][j]: did not take from j + 1 -> n
        // g[i][j]: take from j + 1 -> n

        for(int i = 1; i <= n; i++){
            for(int r = 0; r <= n; r++){
                for(int l = 0; l <= n; l++){
                    f[i][r] = max(f[i][r], f[i - 1][l] + max(0ll, pref[i - 1][r] - pref[i - 1][l]));
                    f[i][r] = max(f[i][r], g[i - 1][l]);
                }
                //cout << i <<" " << r <<" " << dbg(f[i][r]) << "\n";
            }

            if(i > 1){
                for(int r = 0; r <= n; r++){
                    for(int l = 0; l <= n; l++){
                        g[i][r] = max(g[i][r], f[i - 1][l] +
                                      max(0ll, pref[i - 1][r] - pref[i - 1][l]) +
                                      max(0ll, pref[i][l] - pref[i][r]));
                        g[i][r] = max(g[i][r], g[i - 1][l] + max(0ll, pref[i][l] - pref[i][r]));
                    }
                    //cout << i <<" " << r <<" " << dbg(g[i][r]) << "\n";
                }
            }
        }

        ll answer = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= n; j++){
                answer = max(answer, f[i][j]);
                answer = max(answer, g[i][j]);
            }
        }

        return answer;
    }
}

namespace Subtask6{
    bool ckSub(int n){
        return n <= 3000;
    }

    ll process(int n, vector<int>& X, vector<int>& Y, vector<int>& W){
        vector<vector<int>> row(n + 1, vector<int>(n + 1));

        for(int i = 0; i < sz(X); i++){
            row[X[i] + 1][Y[i] + 1] = W[i];
        }

        vector<vector<ll>> pref(n + 1, vector<ll>(n + 1));

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                pref[i][j] = pref[i][j - 1] + row[i][j];
            }
        }

        vector<vector<ll>> f(n + 1, vector<ll>(n + 1));
        vector<vector<ll>> g(n + 1, vector<ll>(n + 1));

        // f[i][j]: did not take from j + 1 -> n
        // g[i][j]: take from j + 1 -> n

        vector<vector<ll>> pMx(n + 1, vector<ll>(n + 1));
        vector<vector<ll>> sMx(n + 1, vector<ll>(n + 1));

        vector<vector<ll>> sgMx(n + 1, vector<ll>(n + 1));
        vector<vector<ll>> pgMx(n + 1, vector<ll>(n + 1));

        for(int i = 1; i <= n; i++){
            for(int l = 0; l <= n; l++){
                pMx[i - 1][l] = f[i - 1][l] - pref[i - 1][l];
                pgMx[i - 1][l] = g[i - 1][l];
                if(l > 0){
                    pMx[i - 1][l] = max(pMx[i - 1][l], pMx[i - 1][l - 1]);
                    pgMx[i - 1][l] = max(pgMx[i - 1][l], pgMx[i - 1][l - 1]);
                }
            }

            for(int r = 0; r <= n; r++){
                f[i][r] = max(f[i][r], pMx[i - 1][r] + pref[i - 1][r]);
                f[i][r] = max(f[i][r], pgMx[i - 1][n]);
                //cout << i <<" " << r <<" " << dbg(f[i][r]) << "\n";
            }

            if(i > 1){
                for(int l = n; l >= 0; l--){
                    sMx[i - 1][l] = f[i - 1][l] + pref[i][l];
                    sgMx[i - 1][l] = g[i - 1][l] + pref[i][l];

                    if(l < n){
                        sMx[i - 1][l] = max(sMx[i - 1][l], sMx[i - 1][l + 1]);
                        sgMx[i - 1][l] = max(sgMx[i - 1][l], sgMx[i - 1][l + 1]);
                    }
                }
                for(int r = 0; r <= n; r++){
                    g[i][r] = max(g[i][r], sMx[i - 1][r] - pref[i][r]);
                    g[i][r] = max(g[i][r], sgMx[i - 1][r] - pref[i][r]);
                    //cout << i <<" " << r <<" " << dbg(g[i][r]) << "\n";
                }
            }
        }

        ll answer = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= n; j++){
                answer = max(answer, f[i][j]);
                answer = max(answer, g[i][j]);
            }
        }

        return answer;
    }
}

namespace Subtask8{
    ll process(int n, vector<int>& X, vector<int>& Y, vector<int>& W){
        vector<vector<pair<int ,ll>>> row(n + 1, vector<pair<int, ll>>(1, make_pair(0, 0)));
        for(int i = 0; i < sz(X); i++){
            row[X[i] + 1].push_back(make_pair(Y[i] + 1, W[i]));
        }

        vector<vector<ll>> pref(n + 1, vector<ll>(2, 0));

        for(int i = 0; i <= n; i++){
            row[i].push_back(make_pair(0, 0));
            row[i].push_back(make_pair(n, 0));
            sort(1 + all(row[i]));

            vector<pair<int, ll>> comp;
            for(int j = 0; j < sz(row[i]); j++){
                if(!sz(comp)){
                    comp.push_back(row[i][j]);
                }
                else if(row[i][j].fi != comp.back().fi){
                    comp.push_back(row[i][j]);
                }
                else{
                    comp.back().se = row[i][j].se;
                }
            }
            row[i] = comp;

            pref[i].resize(sz(row[i]));
            for(int j = 1; j < sz(row[i]); j++){
                pref[i][j] = pref[i][j - 1] + row[i][j].se;
            }
        }

        vector<vector<ll>> f(n + 1, vector<ll>(2, 0));
        vector<vector<ll>> g(n + 1, vector<ll>(2, 0));

        vector<vector<ll>> pMx(n + 1, vector<ll>(2, 0));
        vector<vector<ll>> sMx(n + 1, vector<ll>(2, 0));

        vector<vector<ll>> sgMx(n + 1, vector<ll>(2, 0));
        vector<vector<ll>> pgMx(n + 1, vector<ll>(2, 0));

        for(int i = 1; i <= n; i++){
            f[i].resize(sz(row[i]));
            g[i].resize(sz(row[i]));

            pMx[i - 1].resize(sz(row[i - 1]));
            pgMx[i - 1].resize(sz(row[i - 1]));

            for(int l = 0; l < sz(row[i - 1]); l++){
                pMx[i - 1][l] = f[i - 1][l] - pref[i - 1][l];
                pgMx[i - 1][l] = g[i - 1][l];

                if(l > 0){
                    pMx[i - 1][l] = max(pMx[i - 1][l], pMx[i - 1][l - 1]);
                    pgMx[i - 1][l] = max(pgMx[i - 1][l], pgMx[i - 1][l - 1]);
                }
            }

            for(int r = 0, l = 0; r < sz(row[i]); r++){
                if(r < sz(row[i]) - 1){
                    while(l < sz(row[i - 1]) && row[i - 1][l].fi < row[i][r + 1].fi) l++;
                    --l;
                }
                else l = sz(row[i - 1]) - 1;

                f[i][r] = max(f[i][r], pMx[i - 1][l] + pref[i - 1][l]);
                f[i][r] = max(f[i][r], pgMx[i - 1].back());
            }

            if(i > 1){
                sMx[i - 1].resize(sz(row[i - 1]));
                sgMx[i - 1].resize(sz(row[i - 1]));

                for(int l = sz(row[i - 1]) - 1, r = sz(row[i]) - 1; l >= 0; l--){
                    if(row[i - 1][l].fi <= row[i][r].fi){
                        sMx[i - 1][l] = f[i - 1][l] + pref[i][r];
                        sgMx[i - 1][l] = g[i - 1][l] + pref[i][r];
                    }
                    while(r >= 0 && row[i][r].fi >= row[i - 1][l].fi) r--;

                    if(l < sz(row[i - 1]) - 1){
                        sMx[i - 1][l] = max(sMx[i - 1][l], sMx[i - 1][l + 1]);
                        sgMx[i - 1][l] = max(sgMx[i - 1][l], sgMx[i - 1][l + 1]);
                    }
                }

                for(int l = 0, r = 0; l < sz(row[i]); l++){
                    while(r < sz(row[i - 1]) && row[i - 1][r].fi <= row[i][l].fi) r++;

                    r = max(r - 1, 0);
                    g[i][l] = max(g[i][l], sMx[i - 1][r] - pref[i][l]);
                    g[i][l] = max(g[i][l], sgMx[i - 1][r] - pref[i][l]);
                }
            }
        }

        ll answer = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < sz(row[i]); j++){
                answer = max(answer, f[i][j]);
                answer = max(answer, g[i][j]);
            }
        }

        return answer;
    }
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W){

    return Subtask8::process(n, X, Y, W);
}

• 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