Submission #1213113

#TimeUsernameProblemLanguageResultExecution timeMemory
1213113vivkostovCatfish Farm (IOI22_fish)C++20
52 / 100
806 ms367420 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; struct cell { long long int a,b,c; }; long long int mat[3005][3005],col[3005][3005],n,m; long long int otg,dp[3005][3005],mdp[3005],rdp[3005][3005],sdp[3005][3005],ultdp[3005]; cell a[300005]; void make_dp() { long long int ma1=0,ma2=0,use1=0,use2=0,l1=0,l2=0; for(int j=1;j<=n;j++) { ma1=0; ma2=0; use1=mdp[j-1]; use2=mdp[j-2]; l1=0; l2=0; for(int i=1;i<=n;i++) { ma1+=mat[i][j-1]; ma1=max(ma1,sdp[i][j-1]); if(j>=2) { ma2+=mat[i][j-1]; ma2=max(ma2,rdp[i][j-2]); } if(!l1)use1-=mat[i][j]; if(ma1>=use1) { use1=ma1; l1=1; } if(ma2>=use2) { use2=ma2; } if(j>=3)dp[i][j]=ultdp[j-3]+col[i][j-1]+col[i][j+1]; else dp[i][j]=col[i][j-1]+col[i][j+1]; dp[i][j]=max(dp[i][j],use1+col[i][j+1]); dp[i][j]=max(dp[i][j],use2+col[i][j+1]); sdp[i][j]=max(ma1,rdp[i][j-1]); sdp[i][j]=max(sdp[i][j],use2); sdp[i][j]=max(sdp[i][j],ultdp[j-3]+col[i][j-1]); rdp[i][j]=dp[i][j]-col[i][j+1]; mdp[j]=max(mdp[j],dp[i][j]); otg=max(otg,dp[i][j]); } ultdp[j]=max(ultdp[j],mdp[j]); } //cout<<endl; for(int i=n;i>=1;i--) { for(int j=1;j<=n;j++) { //cout<<dp[i][j]<<" "; } //cout<<endl; } } long long int max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { n=N; m=M; for(int i=1;i<=m;i++) { a[i].a=Y[i-1]+1; a[i].b=X[i-1]+1; a[i].c=W[i-1]; mat[a[i].a][a[i].b]=a[i].c; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { col[i][j]=col[i-1][j]+mat[i][j]; } } for(int i=n;i>=1;i--) { for(int j=1;j<=n;j++) { //cout<<mat[i][j]<<" "; } //cout<<endl; } //cout<<endl; make_dp(); return otg; }
#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...