Submission #1039243

#TimeUsernameProblemLanguageResultExecution timeMemory
1039243Maite_MoraleCatfish Farm (IOI22_fish)C++17
100 / 100
267 ms83540 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define vll vector<ll> #define pll pair<ll,ll> #define vpll vector<pll> #define S second #define F first long long max_weights(int n,int m,vector<int> X,vector<int> Y,vector<int> W) { vector<vll> v (n+5,vll {-1}), w(n+5,vll {0}); vector<vpll> la (n+5,vpll {{-1,0}}); ll r=0; for(int i=0;i<m;i++){ if(X[i]>0)la[X[i]].push_back({Y[i],0}); la[X[i]+1].push_back({Y[i],-W[i]}); la[X[i]+1].push_back({Y[i]-1,0}); la[X[i]+2].push_back({Y[i],0}); } for(int i=0;i<=n;i++){ sort(la[i].begin(),la[i].end()); for(int j=1;j<la[i].size();j++){ if(la[i][j].F==la[i][j-1].F)continue; v[i].push_back(la[i][j].F); w[i].push_back(-la[i][j].S+w[i].back()); //cout<<v[i].back()<<"->"<<w[i].back()<<"\n"; }//cout<<"\n\n"; } vll t1{{}},t2{{}},t3{{}},t4{{}}; vll h2[2]={{},{}},h1[2]={{0},{0}}; for(int i=1;i<=n;i++){ t1=h1[0]; for(int j=0;j<h1[0].size();j++){ t1[j]=t1[j]-w[i-1][j]; if(j>0)t1[j]=max(t1[j],t1[j-1]); //dp[i-1][k<j][0]-co[i][k<j] } t2=h2[1]; for(int j=0;j<h2[0].size();j++){ if(j>0)t2[j]=max(t2[j],t2[j-1]);//dp[i-2][k<j][1] } t3=h2[1];ll p=v[i-1].size()-1; for(int j=h2[0].size()-1;j>=0;j--){ while(p>=0 && v[i-1][p]>v[i-2][j])p--; //cerr<<t3[j]<<" "; if(p>-1)t3[j]=t3[j]+w[i-1][p]; //dp[] // cerr<<t3[j]<<" "; if(j+1<h2[0].size())t3[j]=max(t3[j],t3[j+1]); }//cerr<<"///////////////\n"; t4=h1[1];p=v[i].size()-1; for(int j=h1[1].size()-1;j>=0;j--){ while(p>=0 && v[i][p]>v[i-1][j])p--; if(p>-1)t4[j]=t4[j]+w[i][p]; if(j+1<h1[1].size())t4[j]=max(t4[j],t4[j+1]); } ll p1=-1,p2=-1; vll h[2]={{},{}}; //cerr<<i<<"{\n"; for(int j=0;j<v[i].size();j++){ // cerr<<" "<<v[i][j]<<":\n"; ll dp[2]={0,0}; if(i>=2){ while(p1+1<v[i-1].size() && v[i-1][p1+1]<=v[i][j])p1++; while(p2+1<v[i-2].size() && v[i-1][p2+1]<=v[i][j])p2++; if(p1>-1) dp[0]=max(dp[0],t1[p1]+w[i-1][p1]);//dp[i-1][k][0]-co[i-1][k]+co[i-1][j] //cerr<<"\t"<<dp[0]<<" "<<dp[1]<<"\n"; if(p2>-1) dp[0]=max(dp[0],t2[p2]+w[i-1][p1]);//dp[i-2][k][1] +co[i-1][j] //cerr<<"\t"<<dp[0]<<" "<<dp[1]<<"\n"; if(p2<v[i-2].size()-1)dp[0]=max(dp[0],t3[p2+1]); //dp[i-2][k][1]+co[i-1][k] dp[1]=dp[0]; //cerr<<"\t"<<dp[0]<<" "<<dp[1]<<"\n"; if(p1<v[i-1].size()-1)dp[1]=max(dp[1],t4[p2+1]-w[i][j]); //dp[i-1][k][1]+co [i] [k]-co[i][j] } //cerr<<"\t"<<dp[0]<<" "<<dp[1]<<"\n"; h[0].push_back(dp[0]); h[1].push_back(dp[1]); r=max(h[0].back(),max(r,h[1].back())); } // cerr<<"}\n"; h2[0]=h1[0];h1[0]=h[0]; h2[1]=h1[1];h1[1]=h[1]; } return r; }/* int main() { int N, M; assert(2 == scanf("%d %d", &N, &M)); std::vector<int> X(M), Y(M), W(M); for (int i = 0; i < M; ++i) { assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i])); } long long result = max_weights(N, M, X, Y, W); printf("%lld\n", result); return 0; } //*/ /* 0 0 0 1 0 0 0 3 0 0 5 0 0 0 0 0 2 0 0 0 0 0 0 0 0 */

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j=1;j<la[i].size();j++){
      |                     ~^~~~~~~~~~~~~
fish.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=0;j<h1[0].size();j++){
      |                     ~^~~~~~~~~~~~~
fish.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j=0;j<h2[0].size();j++){
      |                     ~^~~~~~~~~~~~~
fish.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             if(j+1<h2[0].size())t3[j]=max(t3[j],t3[j+1]);
      |                ~~~^~~~~~~~~~~~~
fish.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             if(j+1<h1[1].size())t4[j]=max(t4[j],t4[j+1]);
      |                ~~~^~~~~~~~~~~~~
fish.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<v[i].size();j++){
      |                     ~^~~~~~~~~~~~
fish.cpp:61:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while(p1+1<v[i-1].size() && v[i-1][p1+1]<=v[i][j])p1++;
      |                       ~~~~^~~~~~~~~~~~~~
fish.cpp:62:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 while(p2+1<v[i-2].size() && v[i-1][p2+1]<=v[i][j])p2++;
      |                       ~~~~^~~~~~~~~~~~~~
fish.cpp:67:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 if(p2<v[i-2].size()-1)dp[0]=max(dp[0],t3[p2+1]);         //dp[i-2][k][1]+co[i-1][k]
      |                    ~~^~~~~~~~~~~~~~~~
fish.cpp:70:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 if(p1<v[i-1].size()-1)dp[1]=max(dp[1],t4[p2+1]-w[i][j]); //dp[i-1][k][1]+co [i] [k]-co[i][j]
      |                    ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...