Submission #1210699

#TimeUsernameProblemLanguageResultExecution timeMemory
1210699NicolaikrobCatfish Farm (IOI22_fish)C++17
35 / 100
1105 ms2162688 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) { int sz = n+3; vector<vector<ll>> G(sz, vector<ll> (sz, 0)), PS(sz, vector<ll> (sz, 0)); for(int i = 0; i < m; i++) G[X[i]][Y[i]] = W[i]; for(int c = 0; c < n; c++) { for(int r = 1; r <= n; r++) PS[c][r] = PS[c][r-1]+G[c][r-1]; } vector<vector<ll>> higher(sz, vector<ll> (sz, 0)), best(sz, vector<ll> (sz, 0)); for(int i = 0; i <= n; i++) higher[1][i] = PS[0][i]; for(int i = 0; i <= n; i++) best[1][i] = max(higher[1][i], PS[1][n]-PS[1][i]); for(int c = 2; c < n; c++) { for(int r = 0; r <= n; r++) { ll bt = 0; for(int i = 0; i <= n; i++) bt = max(bt, best[c-2][i]+PS[c-1][max(i,r)]); for(int i = 0; i <= r; i++) bt = max(bt, higher[c-1][i]+PS[c-1][r]-PS[c-1][i]); best[c][r] = higher[c][r] = bt; for(int i = r; i <= n; i++) best[c][r] = max(best[c][r], best[c-1][i]+PS[c][i]-PS[c][r]); } } ll ans = 0; for(int i = 0; i <= n; i++) ans = max(ans, best[n-1][i]); 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...