Submission #1218183

#TimeUsernameProblemLanguageResultExecution timeMemory
1218183vaneaCatfish Farm (IOI22_fish)C++20
9 / 100
967 ms2162688 KiB
#include <bits/stdc++.h> #include "fish.h" using namespace std; using ll = long long; int n, m; ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { n = N; m = M; bool f = true, s = true, t = true; for(int i = 0; i < m; i++) { if(X[i] & 1) f = false; if(X[i] > 1) s = false; if(Y[i] != 0) t = false; } if(f) { ll ans = 0; for(int i = 0; i < m; i++) ans += W[i]; return ans; } if(s) { ll f1 = 0, s1 = 0; vector<ll> pref(n+1); for(int i = 0; i < m; i++) { if(X[i] == 0) f1 += W[i]; else s1 += W[i]; } if(n <= 2) return max(f1, s1); vector<ll> pref1(n+1), pref2(n+1); for(int i = 0; i < m; i++) { if(X[i] == 0) pref1[Y[i]] += W[i]; else pref2[Y[i]] += W[i]; } ll ans = max(f1, s1); for(int i = 1; i <= n; i++) { pref1[i] += pref1[i-1]; pref2[i] += pref2[i-1]; } for(int i = 0; i < n; i++) { ans = max(ans, s1-pref2[i]+pref1[i]); } return ans; } vector<ll> pref1(n+1), pref2(n+1); vector<vector<array<ll, 2>>> adj(n+1); for(int i = 0; i < m; i++) { adj[X[i]].push_back({Y[i]+1, W[i]}); if(X[i] == 0) pref1[Y[i]+1] += W[i]; if(X[i] == 1) pref2[Y[i]+1] += W[i]; } for(int i = 2; i <= n; i++) { pref1[i] += pref1[i-1]; pref2[i] += pref2[i-1]; } vector<vector<array<ll, 2>>> dp(n+1, vector<array<ll, 2>>(n+1)); ll ans = 0; for(int j = 0; j <= n; j++) { for(int k = 0; k <= n; k++) { if(k > j) { dp[1][j][1] = max({dp[1][j][1], pref2[k]-pref2[j]}); } else if(k < j){ dp[1][j][0] = max(dp[1][j][0], pref1[j]-pref1[k]); dp[1][j][1] = max(dp[1][j][1], pref1[j]-pref1[k]); } } ans = max({ans, dp[1][j][0], dp[1][j][1]}); } for(int i = 2; i < n; i++) { swap(pref1, pref2); for(int j = 0; j <= n; j++) pref2[j] = 0; for(auto [y, w] : adj[i]) pref2[y] = w; for(int j = 1; j <= n; j++) pref2[j] += pref2[j-1]; for(int j = 0; j <= n; j++) { for(int k = 0; k <= n; k++) { if(k == j) continue; if(k > j) { dp[i][j][1] = max({dp[i][j][1], dp[i-1][k][1] + pref2[k] - pref2[j], dp[i-1][k][0] + pref2[k] - pref2[j]}); } else { dp[i][j][0] = max({dp[i][j][0], dp[i-1][k][0]+pref1[j]-pref1[k], dp[i-1][k][1]}); } } ans = max({ans, dp[i][j][0], dp[i][j][1]}); } } 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...