Submission #776786

#	Time	Username	Problem	Language	Result	Execution time	Memory
776786		alexander707070	메기 농장 (IOI22_fish)	C++17	14 / 100	1080 ms	156912 KiB

fish

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

int n,m,maxx;

long long pref[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)good[X[i]-1].push_back({Y[i]+1,W[i]});
        if(X[i]<n-1)good[X[i]+1].push_back({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-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:24: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]
   24 |     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: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16