Submission #1075671

#TimeUsernameProblemLanguageResultExecution timeMemory
1075671Sir_Ahmed_ImranCatfish Farm (IOI22_fish)C++17
35 / 100
85 ms12320 KiB
///~~~LOTA~~~/// #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define append push_back #define add insert #define nl '\n' #define ff first #define ss second #define pii pair<int,int> #define pll pair<ll,ll> #define all(x) (x).begin(),(x).end() #define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define terminator main #define N 301 int n; ll hs[N][N]; ll dp[N][N]; ll dp2[N][N]; ll dps(){ for(int i=1;i<=n;i++) dp[0][i]=dp2[0][i]=-1e17; for(int i=1;i<=n;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ if(j<k){ dp[i][j]=max(dp[i][j],dp[i-1][k]+hs[i][k]-hs[i][j]); dp2[i][k]=max(dp2[i][k],dp[i-1][k]+hs[i][k]-hs[i][j]); } else{ dp[i][j]=max(dp[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]); dp2[i][j]=max(dp2[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]); } } dp2[i][j]=max(dp2[i][j],dp[i-1][j]+hs[i][j]); } } ll ans=0; for(int i=0;i<=n;i++) ans=max(ans,max(dp[n][i],dp2[n][i])); return ans; } ll xs(){ ll ans=0; for(int i=0;i<=n;i++) ans=max(ans,hs[1][i]+hs[2][n]-hs[2][i]); return ans; } ll ys(){ for(int i=1;i<2;i++) dp[0][i]=dp2[0][i]=-1e17; for(int i=1;i<=n;i++){ for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ if(j<k){ dp[i][j]=max(dp[i][j],dp[i-1][k]+hs[i][k]-hs[i][j]); dp2[i][k]=max(dp2[i][k],dp[i-1][k]+hs[i][k]-hs[i][j]); } else{ dp[i][j]=max(dp[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]); dp2[i][j]=max(dp2[i][j],dp2[i-1][k]+hs[i-1][j]-hs[i-1][k]); } } dp2[i][j]=max(dp2[i][j],dp[i-1][j]+hs[i][j]); } } ll ans=0; for(int i=0;i<2;i++) ans=max(ans,max(dp[n][i],dp2[n][i])); return ans; } ll max_weights(int M,int m,vector<int> x,vector<int> y,vector<int> w){ n=M; for(int i=0;i<m;i++) hs[x[i]+1][y[i]+1]+=w[i]; for(int i=1;i<=n;i++) for(int j=0;j<n;j++) hs[i][j+1]+=hs[i][j]; if(n<N) return dps(); int mx,my; ll o=0; for(int i=mx=my=0;i<m;i++){ mx=max(mx,x[i]); my=max(my,y[i]); o+=w[i]; } if(mx<2) return xs(); if(my<1) return ys(); return o; }
#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...