제출 #636194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636194		alexander707070	메기 농장 (IOI22_fish)	C++17	0 / 100	1133 ms	867328 KiB

fish

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

int n,m;
int x[MAXM],y[MAXM],w[MAXM];

vector< pair<int,long long> > poss[MAXN],all[MAXN];
vector<long long> dp[MAXN][2][2];
vector<bool> li[MAXN][2][2];

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

    if(li[n][flag][flag2][last])return dp[n][flag][flag2][last];
    li[n][flag][flag2][last]=true;
    dp[n][flag][flag2][last]=-1000000000000000;

    long long sum=0,sum2=0;
    int pt=0,from=0;

    if(flag==0){
        for(int i=0;i<poss[n].size();i++){
            if(poss[n][i].first<=all[n+1][last].first){
                sum+=poss[n][i].second;
            }else break;
        }
        if(n>=1)dp[n][flag][flag2][last]=max( ff(n-1,0,0,0)+sum , ff(n-1,1,1,last) ); 
        else dp[n][flag][flag2][last]=ff(n-1,0,0,0)+sum;

        for(int i=0;i<all[n].size() and all[n][i].first<=all[n+1][last].first;i++){
            while(pt<poss[n].size() and poss[n][pt].first<=all[n][i].first){
                sum-=poss[n][i].second; pt++;
            }
            dp[n][flag][flag2][last]=max(dp[n][flag][flag2][last],ff(n-1,0,0,i)+sum);
        }
    }else{
        while(from<all[n].size() and all[n][from].first<all[n+1][last].first)from++;

        if(flag2==1){
            for(int i=0;i<poss[n+1].size();i++){
                if(poss[n+1][i].first<=all[n+2][last].first)sum2+=poss[n+1][i].second;
            }
        }

        for(int i=from;i<all[n].size();i++){
            while(pt<poss[n+1].size() and poss[n+1][pt].first<=all[n][i].first){
                if(poss[n+1][pt].first>all[n+1][last].first)sum+=poss[n+1][pt].second;
                pt++;
            }
            if(flag2==0){
                dp[n][flag][flag2][last]=max(ff(n-1,1,0,i)+sum,ff(n-1,0,0,i)+sum);
            }else{
                dp[n][flag][flag2][last]=max(ff(n-1,1,0,i)+max(sum,sum2),ff(n-1,0,0,i)+max(sum,sum2));
            }
        }
    }

    return dp[n][flag][flag2][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++){
        x[i+1]=X[i]; y[i+1]=Y[i]; w[i+1]=W[i];
    }
    for(int i=1;i<=m;i++){
        poss[x[i]].push_back({y[i],w[i]});
        //if(x[i]-1>=0)all[x[i]-1].push_back({y[i],w[i]}); 
        //if(x[i]+1<n)all[x[i]+1].push_back({y[i],w[i]});
    }
    for(int i=0;i<n;i++){
        for(int f=0;f<n;f++){
            all[i].push_back({f,0});
        }
    }

    for(int i=0;i<n;i++){
        for(int f=0;f<2;f++){
            for(int k=0;k<2;k++){
                for(int p=0;p<n;p++){
                    dp[i][f][k].push_back(0);
                    li[i][f][k].push_back(false);
                }
            }
        }
    }

    for(int i=0;i<n;i++){
        poss[i].push_back({-1,0});
        all[i].push_back({-1,0});
        sort(poss[i].begin(),poss[i].end());
        sort(all[i].begin(),all[i].end());
    }
    all[n].push_back({-1,0});

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

/*
int main(){

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

    return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int ff(int, int, int, int)':
fish.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i=0;i<poss[n].size();i++){
      |                     ~^~~~~~~~~~~~~~~
fish.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int i=0;i<all[n].size() and all[n][i].first<=all[n+1][last].first;i++){
      |                     ~^~~~~~~~~~~~~~
fish.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             while(pt<poss[n].size() and poss[n][pt].first<=all[n][i].first){
      |                   ~~^~~~~~~~~~~~~~~
fish.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while(from<all[n].size() and all[n][from].first<all[n+1][last].first)from++;
      |               ~~~~^~~~~~~~~~~~~~
fish.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for(int i=0;i<poss[n+1].size();i++){
      |                         ~^~~~~~~~~~~~~~~~~
fish.cpp:47:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=from;i<all[n].size();i++){
      |                        ~^~~~~~~~~~~~~~
fish.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while(pt<poss[n+1].size() and poss[n+1][pt].first<=all[n][i].first){
      |                   ~~^~~~~~~~~~~~~~~~~

• 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