Submission #776806

#	Time	Username	Problem	Language	Result	Execution time	Memory
776806		alexander707070	Catfish Farm (IOI22_fish)	C++17	6 / 100	76 ms	14712 KiB

fish

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
 
int n,m,maxx;
long long pref[10][MAXN],dp[10][MAXN][2],ans;
bool li[10][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]);
        dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,0));
    }
    for(int i=last+1;i<=n;i++){
        if(flag==0)dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,0)+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<5;i++){
        for(int f=1;f<=n;f++){
            pref[i][f]=pref[i][f]+pref[i][f-1];
        }
    }

    if(n>2){
        for(int i=0;i<=n;i++){
            ans=max(ans,pref[0][i]+pref[1][n]-pref[1][i]);
        }
    }else{
        return max(pref[0][n],pref[1][n]);
    }
 
    return ans;
}
 
/*
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: 6 / 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