Submission #829408

#	Time	Username	Problem	Language	Result	Execution time	Memory
829408		erkam	Catfish Farm (IOI22_fish)	C++17	67 / 100	747 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
  
const int N=1e5+5;
const ll inf=1e18;
  
int n,m;
vector<vector<ll>> w;
vector<vector<vector<ll>>> dp;
ll suff[N];
ll val[N];
  
long long max_weights(int _n,int _m,vector<int> X,vector<int> Y,vector<int> W) {
    n=_n,m=_m;
    int mxy=0,mxx=0;
    for(auto x:X)mxx=max(mxx,x+1);
    for(auto x:Y)mxy=max(mxy,x+1);
    n=min(n,mxx+1);
    w=vector<vector<ll>>(n+5,vector<ll>(mxy+5));
    dp=vector<vector<vector<ll>>>(n+5,vector<vector<ll>>(mxy+5,vector<ll>(2)));
    for(int i=0;i<m;i++)w[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=mxy;j++)w[i][j]+=w[i][j-1];
    for(int i=1;i<=n;i++)for(int j=0;j<=mxy;j++)dp[i][j][0]=dp[i][j][1]=-inf;
    for(int i=1;i<=n;i++){
        if(i>=2)for(int j=mxy;j>=0;j--)suff[j]=max(suff[j+1],dp[i-2][j][1]);
        ll tmp=-inf,tmp2=-inf;
        for(int j=0;j<=mxy;j++){
            tmp=max(tmp,dp[i-1][j][0]-w[i][j]-w[i-1][j]);
            dp[i][j][0]=w[i-1][j]+tmp+w[i+1][j];
            if(i>=2){
                tmp2=max(tmp2,dp[i-2][j][0]-w[i-1][j]);
                dp[i][j][0]=max(dp[i][j][0],w[i-1][j]+tmp+w[i+1][j]);
                dp[i][j][0]=max(dp[i][j][0],suff[j]+w[i+1][j]);
            }
        }
        tmp=-inf;
        for(int j=mxy;j>=0;j--){
            tmp=max(tmp,dp[i-1][j][1]);
            dp[i][j][1]=tmp-w[i][j]+w[i+1][j];
            dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]);
        }
    }
    ll ans=0;
    for(int i=0;i<=mxy;i++)ans=max(ans,dp[n][i][1]);
    return ans;
}

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