Submission #1075636

#TimeUsernameProblemLanguageResultExecution timeMemory
1075636Muhammad_AneeqCatfish Farm (IOI22_fish)C++17
18 / 100
56 ms10844 KiB
#include <vector> using namespace std; long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) { bool subt1=1,subt2=1,subt3=1,subt4=(N<=300); for (int i=0;i<M;i++) { if (X[i]%2) subt1=0; if (X[i]>1) subt2=0; if (Y[i]!=0) subt3=0; if (Y[i]>8) subt4=0; } if (subt1) { long long sm=0; for (int i=0;i<M;i++) sm+=W[i]; return sm; } if (subt2) { long long sm[N]={}; long long val[N][2]={}; for (int i=0;i<M;i++) val[Y[i]][X[i]]=W[i]; sm[0]=val[0][1]; for (int i=1;i<N;i++) sm[i]=sm[i-1]+val[i][1]; long long ans=sm[N-1]; long long x=0; for (int i=0;i<N;i++) { x+=val[i][0]; if (N>2) ans=max(ans,x+sm[N-1]-sm[i]); } ans=max(ans,x); return ans; } if (subt3) { long long dp[N][2]={}; int val[N]={}; for (int i=0;i<M;i++) val[X[i]]=W[i]; dp[0][0]=0,dp[0][1]=val[0]; long long ans=0; long long mx=0; for (int i=1;i<N;i++) { if (i>1) dp[i][0]=mx+val[i]; if (i<N-1) dp[i][1]=max(dp[i][0],dp[i-1][0]+val[i]); mx=max(mx,max(dp[i-1][0],dp[i-1][1])); ans=max(ans,max(dp[i][0],dp[i][1])); } return ans; } if (subt4) { vector<vector<vector<long long>>>dp(2,vector<vector<long long>>(N,vector<long long>(9,0))); long long val[N][9]={}; for (int i=0;i<M;i++) val[X[i]][Y[i]]=W[i]; int pre[N][9]={}; for (int i=0;i<N;i++) { pre[i][0]=val[i][0]; for (int j=1;j<9;j++) pre[i][j]=pre[i][j-1]+val[i][j]; } long long mx[N]={}; long long ans=0; for (int i=0;i<9;i++) dp[1][0][i]=pre[0][i]; for (int i=0;i<9;i++) dp[0][1][i]=pre[1][i]; mx[0]=pre[0][8]; for (int i=1;i<N;i++) { for (int j=0;j<9;j++) { if (i>1) dp[0][i][j]=mx[i-2]+pre[i][j]; if (i>2) dp[0][i][j]=max(dp[0][i][j],mx[i-3]+pre[i][j]+pre[i-1][8]-pre[i-1][j]); if (i+1<N) { dp[1][i][j]=max(dp[0][i][j],dp[0][i-1][8]+pre[i][j]); if (j>0) dp[1][i][j]=max(dp[1][i][j],dp[1][i-1][j-1]+val[i][j]); } } mx[i]=max(mx[i-1],max(dp[0][i][8],dp[1][i][8])); } for (int i=0;i<N;i++) for (int j=0;j<9;j++) ans=max(ans,max(dp[0][i][j],dp[1][i][j])); return ans; } 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...