Submission #832953

#TimeUsernameProblemLanguageResultExecution timeMemory
832953Rafi22Catfish Farm (IOI22_fish)C++17
81 / 100
1091 ms142376 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pb push_back #define st first #define nd second #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() int inf=1000000007; ll infl=1000000000000000007; const int N=100007; set<int>S[N]; vector<int>points[N]; vector<ll>DP[2][N]; vector<ll>L[N]; vector<ll>R[N]; vector<ll>M[N]; vector<pair<int,int>>V[N]; ll 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]++; S[X[i]].insert(Y[i]-1); S[X[i]-1].insert(Y[i]); S[X[i]+1].insert(Y[i]); V[X[i]].pb({Y[i],W[i]}); } for(int i=1;i<=n;i++) { S[i].insert(0); sort(all(V[i])); for(auto x:S[i]) points[i].pb(x); DP[0][i].resize(sz(points[i]),0); DP[1][i].resize(sz(points[i]),0); L[i].resize(sz(points[i]),0); R[i].resize(sz(points[i]),0); M[i].resize(sz(points[i]),0); } for(int i=1;i<=n;i++) { vector<pair<int,ll>>P; for(auto [y,c]:V[i-1]) P.pb({y,-c}); for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j}); sort(all(P)); ll sum=0; for(auto [y,c]:P) { if(c>=0) L[i][c]=sum; else sum+=-c; } P.clear(); for(auto [y,c]:V[i+1]) P.pb({y,-c}); for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j}); sort(all(P)); sum=0; for(auto [y,c]:P) { if(c>=0) R[i][c]=sum; else sum+=-c; } P.clear(); for(auto [y,c]:V[i]) P.pb({y,-c}); for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j}); sort(all(P)); sum=0; for(auto [y,c]:P) { if(c>=0) M[i][c]=sum; else sum+=-c; } } for(int i=0;i<sz(points[1]);i++) DP[1][1][i]=-infl; ll ans=0; for(int i=2;i<=n;i++) { vector<pair<int,int>>P; for(int j=0;j<sz(points[i-2]);j++) P.pb({points[i-2][j],-j-1}); //for(auto y:points[i-2]) P.pb({y,0}); for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j}); //for(auto y:points[i]) P.pb({y,1}); sort(all(P)); ll mx=0; for(auto [y,c]:P) { if(c<0) mx=max({mx,DP[0][i-2][-c-1],DP[1][i-2][-c-1]}); else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]); } reverse(all(P)); mx=0; for(auto [y,c]:P) { if(c<0) mx=max(mx,max(DP[0][i-2][-c-1],DP[1][i-2][-c-1])+R[i-2][-c-1]); else DP[0][i][c]=max(DP[0][i][c],mx); } P.clear(); for(int j=0;j<sz(points[i-1]);j++) P.pb({points[i-1][j],-j-1}); for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j}); sort(all(P)); mx=0; for(auto [y,c]:P) { if(c<0) mx=max(mx,DP[0][i-1][-c-1]-M[i-1][-c-1]); else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]); } reverse(all(P)); mx=0; for(auto [y,c]:P) { if(c<0) mx=max(mx,max(DP[0][i-1][-c-1],DP[1][i-1][-c-1])+R[i-1][-c-1]); else DP[1][i][c]=max(DP[1][i][c],mx-M[i][c]); } for(int j=0;j<sz(points[i]);j++) ans=max({ans,DP[0][i][j],DP[1][i][j]}); } return ans; } /* int main() { int n=100000,m=100000; //cin>>n>>m; vector<int>X(m),Y(m),C(m); for(int i=0;i<m;i++) { //cin>>X[i]>>Y[i]>>C[i]; X[i]=rand()%n; Y[i]=rand()%n; C[i]=rand()%1000000+1; } cout<<max_weights(n,m,X,Y,C)<<endl; return 0; }*/
#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...