Submission #1210586

#TimeUsernameProblemLanguageResultExecution timeMemory
1210586simona1230Catfish Farm (IOI22_fish)C++20
100 / 100
192 ms85896 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; int n,m; long long dp[400001][2]; struct catfish { int x,y,w; catfish() {} catfish(int _x,int _y,int _w) { x=_x; y=_y; w=_w; } bool operator<(const catfish&c)const { if(x==c.x)return y<c.y; return x<c.x; } }; catfish a[400001]; int l[100001],r[100001]; long long maxx0[100001],maxx1[100001]; vector<long long> same[100001],nxt[100001],prv[100001],m1[100001],m2[100001],m3[100001]; vector<int> id1[100001],id2[100001]; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { n=N; m=M; for(int i=0; i<n; i++) { X.push_back(i); Y.push_back(n); W.push_back(0); l[i]=-1; r[i]=-2; } for(int i=0; i<X.size(); i++) a[i]= {X[i],Y[i],W[i]}; sort(a,a+X.size()); for(int i=0; i<X.size(); i++) { if(i==0||a[i].x!=a[i-1].x)l[a[i].x]=i; if(i==X.size()-1||a[i].x!=a[i+1].x)r[a[i].x]=i; } long long ans=0; for(int i=0;i<n;i++) { same[i].push_back({0}); for(int j=l[i]+1;j<=r[i];j++) same[i].push_back(same[i][same[i].size()-1]+a[j-1].w); if(i!=n-1) { int k=l[i+1]-1; long long curr=0; for(int j=l[i];j<=r[i];j++) { while(k<r[i+1]&&a[k+1].y<a[j].y) { k++; curr+=a[k].w; } nxt[i].push_back(curr); } } if(i!=0) { int k=l[i-1]-1; long long curr=0; for(int j=l[i];j<=r[i];j++) { while(k<r[i-1]&&a[k+1].y<a[j].y) { k++; curr+=a[k].w; } id1[i].push_back(k-l[i-1]); prv[i].push_back(curr); } } if(i-2>=0) { int k=l[i-2]-1; for(int j=l[i];j<=r[i];j++) { while(k<r[i-2]&&a[k+1].y<a[j].y) { k++; } id2[i].push_back(k-l[i-2]); } } } for(int i=0; i<X.size(); i++) { int x=a[i].x; if(x-1>=0) { long long prec1=prv[x][i-l[x]]; long long prec2=same[x][i-l[x]]; int h=id1[x][i-l[x]]; if(h>=0)dp[i][0]=m1[x-1][h]+prec1; dp[i][1]=m2[x-1][h+1]-prec2; } if(x-2>=0) { long long prec3=prv[x][i-l[x]]; int h=id2[x][i-l[x]]; //cout<<h<<" "<<m3[x-2].size()<<" "<<m2[x-2].size()<<endl; if(h>=0)dp[i][0]=max(dp[i][0],m3[x-2][h]+prec3); dp[i][0]=max(dp[i][0],m2[x-2][h+1]); } ans=max(ans,max(dp[i][0],dp[i][1])); //cout<<a[i].x<<"---- "<<a[i].y<<" "<<a[i].w<<endl; //cout<<dp[i][0]<<" "<<dp[i][1]<<endl; if(x!=n-1)ans=max(ans,max(dp[i][0],dp[i][1])+nxt[x][i-l[x]]); if(i==r[x]) { for(int j=l[x];j<=r[x];j++) { m1[x].push_back(dp[j][0]-same[x][j-l[x]]); if(j!=l[x])m1[x][j-l[x]]=max(m1[x][j-l[x]],m1[x][j-l[x]-1]); m3[x].push_back(max(dp[j][0],dp[j][1])); if(j!=l[x])m3[x][j-l[x]]=max(m3[x][j-l[x]],m3[x][j-l[x]-1]); m2[x].push_back(0); } if(x!=n-1) for(int j=r[x];j>=l[x];j--) { m2[x][j-l[x]]=max(dp[j][0],dp[j][1])+nxt[x][j-l[x]]; if(j!=r[x])m2[x][j-l[x]]=max(m2[x][j-l[x]],m2[x][j-l[x]+1]); } } } 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...