Submission #1073256

#TimeUsernameProblemLanguageResultExecution timeMemory
1073256fv3Catfish Farm (IOI22_fish)C++17
0 / 100
828 ms2097152 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int N, M; vector<vector<ll>> ps, dp; ll get_score(int l, int r, int hl, int hr) { if (l < 0) return -(1ll << 59); if (l == r - 2) return dp[l][hl] + ps[r-1][max(hl, hr)]; else { if (hr < hl) return dp[l][hl] + ps[r][hl] - ps[r][hr]; else return dp[l][hl] + ps[r-1][hr] - ps[r-1][hl]; } } ll max_weights(int N_, int M_, vector<int> X, vector<int> Y, vector<int> W) { N = N_; M = M_; const int mxN = max(N, 9); ps = vector<vector<ll>>(N+1, vector<ll>(mxN)); for (int i = 0; i < M; i++) ps[X[i]][Y[i]] = W[i]; for (int i = 0; i < mxN; i++) { ll sum = 0; for (int j = 0; j < mxN; j++) { sum += ps[i][j]; ps[i][j] = sum; } } dp = vector<vector<ll>>(N, vector<ll>(mxN)); ll res = 0; for (int i = 0; i < N; i++) { res = max(res, ps[1][i]); } for (int r = 1; r < N; r++) { for (int hr = 0; hr < mxN; hr++) { ll mx = ps[r-1][hr]; for (int hl = 0; hl < mxN; hl++) mx = max(mx, get_score(r-2, r, hl, hr)); for (int hl = 0; hl < mxN; hl++) mx = max(mx, get_score(r-1, r, hl, hr)); dp[r][hr] = mx; res = max(res, dp[r][hr] + ps[r+1][hr]); } } return res; }
#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...