Submission #788577

#TimeUsernameProblemLanguageResultExecution timeMemory
788577mosiashvililukaCatfish Farm (IOI22_fish)C++17
100 / 100
278 ms67804 KiB
#include<bits/stdc++.h> #include "fish.h" using namespace std; const long long N=999999999999999999LL; long long a,b,c,d,e,i,j,ii,jj,zx,xc,X[300009],Y[300009],W[300009],DP0[300009],DP1[300009],best[300009],pas; vector <pair <long long, long long> > dp0[300009],dp1[300009],pr[300009]; long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW) { a=NN;b=MM; for(i=0; i<b; i++){ XX[i]++;YY[i]++; X[i+1]=XX[i];Y[i+1]=YY[i];W[i+1]=WW[i]; } for(i=1; i<=b; i++){ //if(Y[i]!=1){ dp0[X[i]].push_back({Y[i]-1,0}); dp1[X[i]].push_back({Y[i]-1,0}); //} pr[X[i]].push_back({Y[i],W[i]}); } for(i=0; i<=a; i++){ if(i!=0){ dp0[i].push_back({a+4,0}); dp1[i].push_back({a+4,0}); } /*dp0[i].push_back({0,0}); dp1[i].push_back({0,0});*/ pr[i].push_back({0,0}); } for(i=0; i<=a; i++){ sort(dp0[i].begin(),dp0[i].end()); sort(dp1[i].begin(),dp1[i].end()); sort(pr[i].begin(),pr[i].end()); for(j=1; j<pr[i].size(); j++){ pr[i][j].second+=pr[i][j-1].second; } } //return max(pr[1].back().second,pr[2].back().second); for(i=1; i<=a+1; i++){ //DP0[i-1] DP1[i-1] best[i-1] DP0[i-1]=-N; DP1[i-1]=-N; for(j=0; j<dp0[i-1].size(); j++){ best[i-1]=max(best[i-1],dp0[i-1][j].second); } if(i==a+1) break; ii=0; for(j=0; j<dp0[i-1].size(); j++){ while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i-1][j].first) ii++; DP0[i-1]=max(DP0[i-1],dp0[i-1][j].second+pr[i][ii].second); } ii=0; for(j=0; j<dp1[i-1].size(); j++){ while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i-1][j].first) ii++; DP1[i-1]=max(DP1[i-1],dp1[i-1][j].second-pr[i-1][ii].second); } //dp1[i] ii=0; for(j=0; j<dp1[i].size(); j++){ while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i][j].first) ii++; dp1[i][j].second=pr[i-1][ii].second+DP1[i-1]; dp1[i][j].second=max(dp1[i][j].second,best[i-1]); } //dp0[i] ii=0; for(j=0; j<dp0[i].size(); j++){ dp0[i][j].second=dp1[i][j].second; while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i][j].first) ii++; zx=-pr[i][ii].second+DP0[i-1]; dp0[i][j].second=max(dp0[i][j].second,zx); } } for(i=1; i<=a; i++){ pas=max(pas,best[i]); } return pas; }

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:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(j=1; j<pr[i].size(); j++){
      |                  ~^~~~~~~~~~~~~
fish.cpp:46:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(j=0; j<dp0[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:51:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(j=0; j<dp0[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i-1][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~
fish.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(j=0; j<dp1[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:57:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i-1][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~~~
fish.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(j=0; j<dp1[i].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~~~
fish.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(j=0; j<dp0[i].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:72:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~
#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...