Submission #776789

#	Time	Username	Problem	Language	Result	Execution time	Memory
776789		alexander707070	Catfish Farm (IOI22_fish)	C++17	35 / 100	1073 ms	154624 KiB

fish

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 3007
using namespace std;
 
int n,m,maxx;
 
long long pref[MAXN][MAXN];
bool in[MAXN][MAXN];
 
vector<long long> dp[MAXN][2];
vector<bool> li[MAXN][2];
 
vector< pair<int,int> > good[MAXN];
 
long long sum(int pos,int l,int r){
    return pref[pos][r]-pref[pos][l];
}
 
long long ff(int pos,int last,int flag){
    if(pos==-1)return 0;
 
    if(li[pos][flag][last])return dp[pos][flag][last];
    li[pos][flag][last]=true;
 
    for(int i=0;i<good[pos].size() and good[pos][i].first<=good[pos+1][last].first;i++){
 
        dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,1)+sum(pos,good[pos][i].first,good[pos+1][last].first));
        dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0));
 
    }
    for(int i=good[pos].size()-1;i>=0 and good[pos][i].first>good[pos+1][last].first;i--){
 
        if(flag==0)dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0)+sum(pos+1,good[pos+1][last].first,good[pos][i].first));
        else dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0));
 
    }
    
    return dp[pos][flag][last];
}
 
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];
 
        if(X[i]>0 and !in[X[i]-1][Y[i]+1]){
            good[X[i]-1].push_back({Y[i]+1,W[i]});
            in[X[i]-1][Y[i]+1]=true;
        }
        if(X[i]<n-1 and !in[X[i]+1][Y[i]+1]){
            good[X[i]+1].push_back({Y[i]+1,W[i]});
            in[X[i]+1][Y[i]+1]=true;
        }
    }
 
    for(int i=0;i<n;i++){
        for(int f=1;f<=n;f++){
            pref[i][f]+=pref[i][f-1];
        }
    }
 
    for(int i=0;i<=n;i++){
        good[i].push_back({0,0});
        sort(good[i].begin(),good[i].end());
        dp[i][0].resize(good[i+1].size()+5);
        dp[i][1].resize(good[i+1].size()+5);
 
        li[i][0].resize(good[i+1].size()+5);
        li[i][1].resize(good[i+1].size()+5);
    }
 
    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";
}
*/

Compilation message (stderr)

fish.cpp: In function 'long long int ff(int, int, int)':
fish.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<good[pos].size() and good[pos][i].first<=good[pos+1][last].first;i++){
      |                 ~^~~~~~~~~~~~~~~~~

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