Submission #629449

#TimeUsernameProblemLanguageResultExecution timeMemory
629449handlenameCatfish Farm (IOI22_fish)C++17
100 / 100
505 ms65572 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair vector<pair<int,long long> > arr[100005]; long long qry(int col,int height){ //prefixsum of col to height if (arr[col].empty()) return 0; pair<int,long long> lol=mp(height,1e18); int pos=upper_bound(arr[col].begin(),arr[col].end(),lol)-arr[col].begin(); pos--; return arr[col][pos].second; } vector<long long> dp1[100005]; //col,height,increasing vector<long long> dp2[100005]; //col,height,decreasing vector<long long> whack[100005]; long long max_weights(int n,int m,vector<int> x,vector<int> y,vector<int> w){ for (int i=0;i<m;i++){ x[i]++; y[i]++; arr[x[i]].pb(mp(y[i],w[i])); } for (int i=1;i<=n;i++){ arr[i].pb(mp(0,0)); sort(arr[i].begin(),arr[i].end()); for (int j=1;j<(int)arr[i].size();j++){ arr[i][j].second+=arr[i][j-1].second; } for (auto j:arr[i]){ whack[i].pb(j.first); whack[i+1].pb(j.first); whack[i-1].pb(j.first); } } for (int i=0;i<=n;i++){ sort(whack[i].begin(),whack[i].end()); whack[i].erase(unique(whack[i].begin(),whack[i].end()),whack[i].end()); for (int j=0;j<(int) whack[i].size();j++){ dp1[i].pb(0); dp2[i].pb(0); } } for (int i=1;i<=n;i++){ //col long long maxi=0,id=0; for (int j=0;j<(int)whack[i].size();j++){ int k=whack[i][j]; while (id<(int)whack[i-1].size() && whack[i-1][id]<=k){ maxi=max(maxi,dp1[i-1][id]-qry(i,whack[i-1][id])-qry(i-1,whack[i-1][id])); id++; } dp1[i][j]=maxi+qry(i-1,k)+qry(i+1,k); } if (i>=2){ maxi=0; id=0; for (int j=0;j<(int)whack[i].size();j++){ int k=whack[i][j]; while (id<(int)whack[i-2].size() && whack[i-2][id]<=k){ maxi=max(maxi,dp2[i-2][id]-qry(i-1,whack[i-2][id])); id++; } dp1[i][j]=max(dp1[i][j],maxi+qry(i-1,k)+qry(i+1,k)); } maxi=0; id=whack[i-2].size()-1; for (int j=whack[i].size()-1;j>=0;j--){ int k=whack[i][j]; while (id>=0 && whack[i-2][id]>=k){ maxi=max(maxi,dp2[i-2][id]); id--; } dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,k)); } } maxi=0; id=whack[i-1].size()-1; for (int j=whack[i].size()-1;j>=0;j--){ int k=whack[i][j]; while (id>=0 && whack[i-1][id]>=k){ maxi=max(maxi,dp2[i-1][id]); id--; } dp2[i][j]=maxi+qry(i+1,k)-qry(i,k); } for (int j=0;j<(int)whack[i].size();j++){ dp2[i][j]=max(dp2[i][j],dp1[i][j]); } } long long ans=0; for (int j=0;j<(int)dp2[n].size();j++){ ans=max(ans,dp2[n][j]); } return ans; }
#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...