Submission #834302

#TimeUsernameProblemLanguageResultExecution timeMemory
834302gagik_2007Catfish Farm (IOI22_fish)C++17
35 / 100
409 ms439504 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=307; ll n,m,k; ll pf[N][N]; ll dp[N][N][N]; ll dh[N][N][N]; ll max_weights(int NN, int MM, vector<int> X, vector<int> Y, vector<int> W) { n=NN; m=MM; for(int i=0;i<m;i++){ pf[X[i]][Y[i]+1]=W[i]; } for(int i=0;i<n;i++){ for(int j=1;j<=n;j++){ pf[i][j]+=pf[i][j-1]; } } for(int i=0;i<=n;i++){ dp[0][0][i]=pf[1][i]; // cout<<"0, 0, "<<i<<": "<<dp[0][0][i]<<endl; } // cout<<endl; ll ans=0; for(int i=1;i<n;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ ll res=0; res-=pf[i][min(k,j)]; if(i!=n-1){ res+=pf[i+1][j]; } // cout<<i<<", "<<k<<", "<<j<<": "; ll mres=res; if(j<=k)mres+=dp[i-1][0][k]; else{ mres+=max(dp[i-1][j][k],dh[i-1][j-1][k]+pf[i-1][j]); } dp[i][k][j]=max(dp[i][k][j],mres); ans=max(ans,dp[i][k][j]); dh[i][k][j]=dp[i][k][j]-pf[i][max(j,k)]; // cout<<dp[i][k][j]<<"\n"; if(k!=0)dh[i][k][j]=max(dh[i][k][j],dh[i][k-1][j]); } for(int k=n-1;k>=0;k--){ dp[i][k][j]=max(dp[i][k][j],dp[i][k+1][j]); } // cout<<endl; } // cout<<endl; } 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...