제출 #776809

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

fish

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 100007
using namespace std;
 
int n,m,maxx;
 
vector<long long> dp[MAXN][2];
vector<bool> li[MAXN][2];
 
vector< pair<int,int> > good[MAXN],s[MAXN];

long long sum(int pos,int l,int r){
    int res=0;
    for(int i=0;i<s[pos].size();i++){
        if(s[pos][i].first>=l and s[pos][i].first<=r)res+=s[pos][i].second;
    }
    return res;
}
 
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++){
        s[X[i]].push_back({Y[i]+1,W[i]});
 
        good[X[i]-1].push_back({Y[i]+1,W[i]});
        good[X[i]+1].push_back({Y[i]+1,W[i]});
    }
 
    for(int i=0;i<=n;i++){
        good[i].push_back({0,0});
        sort(good[i].begin(),good[i].end());
        sort(s[i].begin(),s[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";
}
*/

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

fish.cpp: In function 'long long int sum(int, int, int)':
fish.cpp:16: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]
   16 |     for(int i=0;i<s[pos].size();i++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp: In function 'long long int ff(int, int, int)':
fish.cpp:28: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]
   28 |     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: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16