Submission #628466

#	Time	Username	Problem	Language	Result	Execution time	Memory
628466		guangxuan	Catfish Farm (IOI22_fish)	C++17	100 / 100	213 ms	27536 KiB

fish

#include "fish.h"
#define F first
#define S second
#include <bits/stdc++.h>
typedef long long ll;

const ll INF= 1LL<<60;
using namespace std;
typedef pair<int, ll> pil;

long long max_weights(int N, int M, std::vector<int> X, vector<int> Y,
                      vector<int> W) {
    for(int i=0;i<M;i++){
        Y[i]+=1;
    }
    vector<pil> rs[N];
    for(int i=0;i<M;i++){
        rs[X[i]].emplace_back(Y[i],W[i]);
    }
    for(int i=0;i<N;i++){
        rs[i].emplace_back(0,0);
        sort(rs[i].begin(),rs[i].end());
        rs[i].emplace_back(N+2,0);
        for(int j=1;j<(int)rs[i].size();j++){
            rs[i][j].S+=rs[i][j-1].S;
        }
    }
    ll dp[2][3][N+2]; // (0, h[i-1]), (h[i-1] <= h[i], h[i]), (h[i-1]>h[i], h[i])
    memset(dp,0,sizeof dp);
    for(int i=0,k=0;i<(int)rs[0].size();i++){
        while(k+1<(int)rs[1].size() && rs[0][i].F>rs[1][k+1].F){
            k++;
        }
        dp[1][0][i]=rs[1][k].S;
    }
    for(int i=0,k=0;i<(int)rs[1].size();i++){
        while(k+1<(int)rs[0].size() && rs[1][i].F>rs[0][k+1].F ){
            k++;
        }
        dp[1][1][i]=rs[0][k].S;
        dp[1][2][i]=rs[1].back().S-rs[1][max(i-1,0)].S;
    }
    for(int i=2;i<N;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<(int)max(rs[i-1].size(),rs[i].size());k++){
                dp[i&1][j][k]=0;
            }   
        }
        int rss = rs[i].size();
        int ps = rs[i-1].size();
        int pps = rs[i-2].size();
        for(int j=0, k = 0;j<ps;j++){
            while(k+1<rss && rs[i-1][j].F > rs[i][k+1].F){
                k++;
            }
            dp[i&1][0][j]=max(dp[(i&1)^1][1][j],dp[(i&1)^1][2][j])+rs[i][k].S;
        }
        //0,k -> 1,j
        ll cmax = -INF;
        for(int j=0, k =0, l=0, l2=0;j<rss;j++){
            while(k<pps && rs[i][j].F>rs[i-2][k].F){
                while(l+1<ps && rs[i-2][k].F > rs[i-1][l+1].F){
                    l++;
                }
                cmax = max(cmax,dp[(i&1)^1][0][k]+rs[i-1][l].S);
                k++;
            }
            while(l2+1<ps && rs[i][j].F > rs[i-1][l2+1].F){
                l2++;
            }
            dp[i&1][1][j]=max(dp[i&1][1][j],cmax-rs[i-1][l2].S);
        }
        cmax = -INF;
        for(int j=rss-1,k=pps-1 ;j>=0;j--){
            while(k>=0 && rs[i][j].F<=rs[i-2][k].F){
                cmax = max(cmax,dp[(i&1)^1][0][k]);
                k--;
            }
            dp[i&1][1][j]=max(dp[i&1][1][j],cmax);
        }
        //1,k -> 1,j
        cmax = -INF;
        for(int j=0, k=0, k2=0;j<rss;j++){
            while(k<ps && rs[i][j].F>=rs[i-1][k].F){
                cmax = max(cmax, dp[(i&1)^1][1][k]-rs[i-1][max(k-1,0)].S);
                k++;
            }
            while(k2+1<ps && rs[i][j].F > rs[i-1][k2].F)k2++;
            dp[i&1][1][j]=max(dp[i&1][1][j],cmax+rs[i-1][max(k2-1,0)].S);
        }
        //1,k 2,k -> 2,j
        cmax = -INF;
        for(int j=rss-1, k = ps-1, l = rss-1;j>=0;j--){
            while(k>=0 && rs[i][j].F<rs[i-1][k].F){
                while(l-1>=0 && rs[i-1][k].F<=rs[i][l].F)l--;
                cmax = max(cmax, max(dp[(i&1)^1][1][k],dp[(i&1)^1][2][k])+rs[i][l].S);
                k--;
            }
            dp[i&1][2][j]=max(dp[i&1][2][j],cmax-rs[i][max(j-1,0)].S);
        }
    }
    ll ans = 0;
    /*for(int i=0;i<=N;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<=N;k++){
                cout << dp[i&1][j][k] << ' ';
            }
            cout << endl;
        }
        cout << endl;
    }*/
    for(int k=0;k<(int)rs[N-2].size();k++)ans = max(ans, dp[(N-1)&1][0][k]);
    for(int j=1;j<3;j++)
        for(int k=0;k<(int)rs[N-1].size();k++)ans = max(ans, dp[(N-1)&1][j][k]);
    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