Submission #659489

#TimeUsernameProblemLanguageResultExecution timeMemory
659489pere_gilCatfish Farm (IOI22_fish)C++17
61 / 100
866 ms2097152 KiB
#include "fish.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; #define all(x) x.begin(),x.end() void fill(vector<ll> &pier, vector<ll> &fish, vector<ll> &v){ for(int i=0,j=0;i<(int)pier.size();) if(j==(int)fish.size()-1 || (pier[i]>=fish[j] && pier[i]<fish[j+1])) v[i++]=j; else j++; } ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){ vector<ll> sum[n],fish[n],temp_pier[n],pier[n]; vector<pair<ll,ll>> inf_fish[n]; for(int i=0;i<m;i++) inf_fish[x[i]].push_back({y[i]+1,w[i]}); for(int i=0;i<n;i++){ sum[i].push_back(0); fish[i].push_back(0); temp_pier[i].push_back(0); sort(all(inf_fish[i])); for(int j=0;j<(int)inf_fish[i].size();j++){ fish[i].push_back(inf_fish[i][j].first); sum[i].push_back(inf_fish[i][j].second); if(i) temp_pier[i-1].push_back(inf_fish[i][j].first); if(i!=n-1) temp_pier[i+1].push_back(inf_fish[i][j].first); } } for(int i=0;i<n;i++){ sort(all(temp_pier[i])); pier[i].push_back(temp_pier[i][0]); for(int j=1;j<(int)temp_pier[i].size();j++) if(temp_pier[i][j]!=temp_pier[i][j-1]) pier[i].push_back(temp_pier[i][j]); for(int j=1;j<(int)fish[i].size();j++) sum[i][j]+=sum[i][j-1]; } vector<ll> left[n],me[n],right[n]; for(int i=0;i<n;i++){ left[i].assign(pier[i].size(),0); me[i].assign(pier[i].size(),0); right[i].assign(pier[i].size(),0); if(i) fill(pier[i],fish[i-1],left[i]); fill(pier[i],fish[i],me[i]); if(i!=n-1) fill(pier[i],fish[i+1],right[i]); } vector<vector<ll>> dec[n],inc[n]; for(int i=0;i<n;i++){ int j=(i) ? pier[i-1].size() : 1; int k=pier[i].size(); dec[i].assign(j,vector<ll>(k,0)); inc[i].assign(j,vector<ll>(k,0)); } for(int i=0;i<(int)pier[0].size();i++) for(int j=0;j<(int)pier[1].size();j++){ ll aux=0; if(pier[0][i]>=pier[1][j]) aux+=sum[1][right[0][i]]-sum[1][me[1][j]]; else aux+=sum[0][left[1][j]]-sum[0][me[0][i]]; dec[1][i][j]=inc[1][i][j]=aux; } for(int i=2;i<n;i++){ for(int j=0;j<(int)pier[i-1].size();j++){ //decreasing: if(pier[i-1][j]){ ll prev=0; for(int k=0;k<(int)pier[i-2].size();k++){ if(pier[i-2][k]<pier[i-1][j]) continue; prev=max(prev,max(dec[i-1][k][j],inc[i-1][k][j])); } for(int k=0;k<(int)pier[i].size();k++){ if(pier[i][k]>pier[i-1][j]) break; dec[i][j][k]+=prev; dec[i][j][k]+=sum[i][right[i-1][j]]-sum[i][me[i][k]]; } } else{ ll prev=0; int pos=0; for(int k=0;k<(int)pier[i-2].size();k++){ ll aux=max(dec[i-1][k][j],inc[i-1][k][j]); if(aux>=prev){ prev=aux; pos=k; } } for(int k=0;k<(int)pier[i].size();k++){ dec[i][j][k]+=prev; if(pier[i][k]<pier[i-2][pos]) continue; dec[i][j][k]+=sum[i-1][left[i][k]]-sum[i-1][right[i-2][pos]]; } } //increasing: ll prev=0; for(int k=0;k<(int)pier[i-2].size();k++){ if(pier[i-2][k]>pier[i-1][j]) break; prev=max(prev,inc[i-1][k][j]); if(!pier[i-2][k]) prev=max(prev,dec[i-1][k][j]); } for(int k=0;k<(int)pier[i].size();k++){ inc[i][j][k]+=prev; if(pier[i-1][j]>=pier[i][k]) inc[i][j][k]+=sum[i][right[i-1][j]]-sum[i][me[i][k]]; else inc[i][j][k]+=sum[i-1][left[i][k]]-sum[i-1][me[i-1][j]]; } } } ll res=0; for(int i=0;i<(int)pier[n-2].size();i++) for(int j=0;j<(int)pier[n-1].size();j++) res=max({res,dec[n-1][i][j],inc[n-1][i][j]}); return res; }
#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...