Submission #776721

#	Time	Username	Problem	Language	Result	Execution time	Memory
776721		alexander707070	Catfish Farm (IOI22_fish)	C++17	12 / 100	74 ms	15596 KiB

fish

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

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

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

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

    dp[pos]=ff(pos-1);

    if(pos==n-1){
        dp[pos]=max(dp[pos],ff(pos-2)+sum[pos]);
    }else if(pos>=2){
        dp[pos]=max(dp[pos], max(ff(pos-3)+sum[pos]+sum[pos-1],ff(pos-2)+sum[pos]) );
    }else if(pos==1){
        dp[pos]=max(dp[pos],ff(pos-2)+sum[pos]);
    }else if(pos==0){
        dp[pos]=max(dp[pos],ff(pos-1)+sum[pos]);
    }

    return dp[pos];
}

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++){
        sum[X[i]]+=W[i];
        maxx=max(maxx,X[i]);
    }

    if(n==2 or maxx==1)return max(sum[0],sum[1]);
    return ff(n-1);
}

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

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