Submission #1210970

#TimeUsernameProblemLanguageResultExecution timeMemory
1210970nerrrminCatfish Farm (IOI22_fish)C++20
32 / 100
744 ms16452 KiB
#include "fish.h" #include<bits/stdc++.h> #define pb push_back #include <vector> using namespace std; const int maxn = 305; int n, m; vector < pair < int, int > > g[200000]; long long dp[maxn][10][10]; long long pref[maxn][maxn], a[maxn][maxn]; long long get(int col, int l, int r) { if(r < l)return 0; if(col > n)return 0; long long val = pref[col][r]; if(l)val -= pref[col][l-1]; return val; } long long p[4][200000]; long long get_p(long long col, long long l, long long r) { if(r < l)return 0; if(col > n)return 0; long long val = p[col][r]; if(l)val -= p[col][l-1]; return val; } long long val[200000], d[200000][2][2]; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { n = N; m = M; long long sum = 0, group1 = 1, group2 = 1, group3 = 1; for (int i = 0; i < m; ++ i) { if(X[i] % 2 == 1)group1 = 0; if(X[i] > 1)group2 = 0; if(Y[i] > 0)group3 = 0; X[i] ++; Y[i] ++; g[X[i]].pb(make_pair(Y[i], W[i])); sum += W[i]; if(n <= 300)a[X[i]][Y[i]] = W[i]; if(X[i] <= 2)p[X[i]][Y[i]] += W[i]; if(Y[i] == 1)val[X[i]] += W[i]; } if(group1)return sum; if(group2) { long long sum1 = 0, sum2 = 0; for (auto &[y, w]: g[1]) sum1 += w; for (auto &[y, w]: g[2]) sum2 += w; long long ans = max(sum1, sum2); if(n > 2) { for (int i = 1; i <= 2; ++ i) { for (int j = 1; j <= n; ++ j) p[i][j] += p[i][j-1]; } for (int i = 0; i <= n; ++ i) { long long curr = get_p(1, 1, i) + get_p(2, i+1, n); ans = max(ans, curr); } } return ans; } if(group3) { d[1][0][0] = 0; d[1][0][1] = 0; long long ans = 0; if(n > 1)ans = val[2]; for (int i = 2; i <= n; ++ i) { /// 0 d[i][0][0] = max(d[i-1][0][0], d[i-1][1][0]); d[i][1][0] = max(d[i-1][0][1], d[i-1][1][1]) + val[i]; /// 1 d[i][0][1] = max(d[i-1][0][0] + val[i-1], d[i-1][1][0]); d[i][1][1] = max(d[i-1][0][1], d[i-1][1][1]); ans = max(ans, max(d[i][0][1], d[i][1][1]) + val[i+1]); } return ans; } for (int i = 0; i <= n; ++ i) { pref[i][0] = a[i][0]; for (int j = 1; j <= n; ++ j) pref[i][j] = pref[i][j-1] + a[i][j]; } long long ans = 0; for (int last = 0; last <= 9; ++ last) { for (int pre = 0; pre <= 9; ++ pre) { dp[2][pre][last] = get(1, pre+1, last); ans = max(ans, dp[2][pre][last] + get(3, 1, last)); } } for (int i = 2; i <= n; ++ i) { for (int j = 0; j <= 8; ++ j) { for (int last = 0; last <= 9; ++ last) { for (int pre = 0; pre <= 9; ++ pre) { long long curr = dp[i-1][pre][last] + get(i, j+1, last) + get(i-1, max(pre, last) + 1, j); dp[i][last][j] = max(dp[i][last][j], curr); ans = max(ans, dp[i][last][j] + get(i+1, 1, j)); } } } } 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...