Submission #1055695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055695		vjudge1	Catfish Farm (IOI22_fish)	C++17	0 / 100	595 ms	445004 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int>fishies[3002];
ll FIS2;
ll dp[3010][2][3010],fishiess[3010][3010];
ll first[3010][3010];
ll sec[3010][301],third[3010][3010],overal[3010][3010];
inline ll ones(int col,int len){
    return fishiess[col][len];
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
    for(int i=0;i<M;i++)
        fishies[X[i]+1].insert(Y[i]+1),
        fishiess[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N+1;j++)
            fishiess[i][j]+=fishiess[i][j-1];
    for(int i=1;i<=N;i++)
        fishies[i].insert(1),
        fishies[i].insert(N+1);
    fishies[N+1].insert(0);
    for(auto i:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    for(int j=0;j<=N;j++){
        overal[1][j]=first[1][j]=max(dp[1][0][j],dp[1][1][j]);
        first[1][j]+=ones(2,j);sec[1][j]=dp[1][0][j];
        third[1][j]=dp[1][1][j]-ones(1,j)-ones(2,j);
    }
    for(int j=N;~j;j--)
        overal[1][j]=max(overal[1][j],overal[1][j+1]),
        sec[1][j]=max(sec[1][j],sec[1][j+1]);
    for(int j=1;j<=N;j++)
        first[1][j]=max(first[1][j],first[1][j-1]),
        third[1][j]=max(third[1][j],third[1][j-1]);
    for(int i=2;i<=N;i++){
        for(auto rw:fishies[i]) {
            ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
            dp[i][1][rw-1]=cons+max(first[i-2][rw-1],overal[i-2][rw]-ones(i-1,rw-1));
        }
        for(auto rw2:fishies[i])
            dp[i][0][rw2-1]=max(0ll,ones(i+1,rw2-1)-ones(i,rw2-1)+sec[i-1][rw2]);
        for(auto rw2:fishies[i]){
            ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
            dp[i][1][rw2-1]=third[i-1][rw2]+cons;
            dp[i][0][rw2-1]=max(dp[i][0][rw2-1],overal[i-1][rw2]-ones(i,rw2-1)-ones(i-1,rw2-1))+cons;
        }
        for(int j=0;j<=N;j++){
            overal[i][j]=first[i][j]=max(dp[i][0][j],dp[i][1][j]);
            first[i][j]-=ones(i+1,j);sec[i][j]=dp[i][0][j];
            third[i][j]=dp[i][1][j]-ones(i,j)-ones(i+1,j);
        }
        for(int j=N;~j;j--)
            overal[i][j]=max(overal[i][j],overal[i][j+1]),
            sec[i][j]=max(sec[i][j],sec[i][j+1]);
        for(int j=1;j<=N;j++)
            first[i][j]=max(first[i][j],first[i][j-1]),
            third[i][j]=max(third[i][j],third[i][j-1]);
    }
    return overal[N][0];
}

• Subtask 1: 0 / 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