Submission #729761

#TimeUsernameProblemLanguageResultExecution timeMemory
729761Nahian9696Catfish Farm (IOI22_fish)C++17
32 / 100
87 ms21856 KiB
#include "fish.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define f0(i, n) for(int i = 0; i < (n); i++) #define f1(i, n) for(int i = 1; i <= (n); i++) #define pb push_back #define ff first #define ss second typedef vector<int> vi; typedef long long ll; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { bool allxeven = true; bool allxleq1 = true; bool ally0 = true; f0(i, M) { if(X[i] % 2 == 1) allxeven = false; if(X[i] > 1) allxleq1 = false; if(Y[i] != 0) ally0 = false; } if (allxeven) { ll ret = 0; f0(i, M) ret += W[i]; return ret; } if(allxleq1) { ll ret = 0; ll ans = 0; int arr[N][2]; f0(i, N) arr[i][0] = 0, arr[i][1] = 0; f0(i, M) { arr[Y[i]][X[i]] = W[i]; } if(N == 2) { return max(arr[0][0] + arr[1][0], arr[0][1] + arr[1][1]); } f0(i, N) { ans += arr[i][1]; } ret = ans; f0(i, N) { ans -= arr[i][1]; ans += arr[i][0]; ret = max(ret, ans); } return ret; } if(ally0) { int arr[N]; f0(i, N) arr[i] = 0; f0(i, M) arr[X[i]] = W[i]; ll dp[N][4]; dp[0][0] = -1e18; dp[0][1] = -1e18; dp[0][2] = 0; dp[0][3] = arr[0]; dp[1][0] = 0; dp[1][1] = arr[1]; dp[1][2] = arr[0]; dp[1][3] = -1e18; f1(i, N-2) { dp[i+1][0] = max(dp[i][0], dp[i][2]); dp[i+1][1] = max(dp[i][0], dp[i][2]) + arr[i+1]; dp[i+1][2] = max(dp[i][1], dp[i][3]); dp[i+1][3] = dp[i][1] + arr[i+1]; } return max({ dp[N-1][0], dp[N-1][1], dp[N-1][2] }); } ll arr[N][10]; f0(i, N) f0(j, 10) arr[i][j] = 0; f0(i, M) { arr[X[i]][Y[i]+1] = W[i]; } ll prefarr[N][10]; f0(i, N) prefarr[i][0] = 0; f0(i, N) f1(j, 9) { prefarr[i][j] = prefarr[i][j-1] + arr[i][j]; } ll dp[N][10][10][10]; ll mxdp[N][10][10]; f0(i, 10) f0(j, 10) { f0(k, 10) dp[0][i][j][k] = 0; mxdp[0][i][j] = 0; } f0(i, 10) f0(j, 10) { ll val = 0; if(i > j) { for(int x = j+1; x <= i; x++) val += arr[0][x]; } else { for(int x = i+1; x <= j; x++) val += arr[1][x]; } mxdp[1][i][j] = val; f0(k, 10) { dp[1][i][j][k] = val; } } f1(col, N-2) { f0(i, 10) f0(j, 10) { ll mx = 0; f0(k, 10) { dp[col+1][i][j][k] = mxdp[col][j][k]; if(max(j, k) <= i) { dp[col+1][i][j][k] += prefarr[col][i] - prefarr[col][max(j, k)]; } if(j >= i) dp[col+1][i][j][k] += prefarr[col+1][j] - prefarr[col+1][i]; mx = max(mx, dp[col+1][i][j][k]); } mxdp[col+1][i][j] = mx; // cout << mx << endl; } } ll ans = 0; f0(i, 10) f0(j, 10) ans = max(ans, mxdp[N-1][i][j]); return ans; return 9; }
#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...