Submission #776773

#	Time	Username	Problem	Language	Result	Execution time	Memory
776773		alexander707070	Catfish Farm (IOI22_fish)	C++17	0 / 100	724 ms	154376 KiB

fish

#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;

int n,m,maxx;
long long pref[MAXN][MAXN],dp[MAXN][MAXN][2];
bool li[MAXN][MAXN][2];

long long ff(int pos,int last,int flag){
    if(pos==-1)return 0;

    if(li[pos][last][flag])return dp[pos][last][flag];
    li[pos][last][flag]=true;

    for(int i=0;i<=last;i++){
        dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,1)+pref[pos][last]-pref[pos][i]);
    }
    for(int i=last+1;i<=n;i++){
        if(flag==0)dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,1)+pref[pos+1][i]-pref[pos+1][last]);
        else dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,0));
    }
    
    return dp[pos][last][flag];
}

long long max_weights(int N, int M,vector<int> X,vector<int> Y,vector<int> W){
    n=N; m=M;
    for(int i=0;i<m;i++){
        pref[X[i]][Y[i]+1]+=W[i];
    }

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

    return ff(n-1,0,0);
}

/*
int main(){
    cout<<max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3})<<"\n";
}
*/

• 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