제출 #1073209

#제출 시각아이디문제언어결과실행 시간메모리
1073209fv3메기 농장 (IOI22_fish)C++17
0 / 100
1146 ms2097152 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int N, M; vector<int> X, Y, W; vector<vector<ll>> ps, v, dp; ll get_score(int l, int r, int hl, int hr) { if (l < 0) return 0; const int mn_h = min(hl, hr); if (l == r - 1) { return dp[l][hl] - ps[r][mn_h] - ps[l][mn_h]; } if (l == r - 2) return dp[l][hl] - ps[l+1][mn_h]; return dp[l][hl]; } ll max_weights(int N_, int M_, vector<int> X_, vector<int> Y_, vector<int> W_) { N = N_; M = M_; X = X_; Y = Y_; W = W_; ps = v = vector<vector<ll>>(N+1, vector<ll>(N)); for (int i = 0; i < M; i++) v[X[i]][Y[i]] = W[i]; for (int i = 0; i < N; i++) { ll sum = 0; for (int j = 0; j < N; j++) { sum += v[i][j]; ps[i][j] = sum; } } dp = vector<vector<ll>>(N, vector<ll>(N)); ll res = 0; for (int i = 0; i < N; i++) { dp[0][i] = ps[1][i]; res = max(res, dp[0][i]); } for (int r = 1; r < N; r++) { for (int hr = 0; hr < N; hr++) { ll mx = max(0ll, dp[r-1][N-1] - ps[r-1][hr] - ps[r][hr]); for (int l = r - 3; l < r - 1; l++) { if (l < 0) continue; for (int hl = 0; hl < N; hl++) mx = max(mx, get_score(l, r, hl, hr)); } dp[r][hr] = ps[r-1][hr] + ps[r+1][hr] + mx; res = max(res, dp[r][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...