| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 636808 | dsabolic | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 305;
ll dp[N][N][2][2];
int n, m;
vector<int> x;
vector<int> y;
vector<int> w;
int ima(int i, int j) {
auto it = lower_bound(x.begin(), x.end(), i);
if(it == x.end()) return 0;
if(*it == i && y[it - x.begin()] == j) return w[it - x.begin()];
else return 0;
}
ll solve(int i, int hp, bool f1, bool f2) {
if(i == n) return 0;
ll& ret = dp[i][hp][f1][f2];
if(ret != -1) return ret;
ret = 0;
if(f2) {
for(int h = 0; h <= n; ++h) {
if(h == 0) {
ret = max(ret, solve(i + 1, 0, 0, 1));
} else {
//ret = max(ret, solve(i + 1, 0, 0, 0) + ima(i - 1, h) + ima(i + 1, h));
if(hp == h) ret = max(ret, solve(i + 1, h, 0, 0) + ima(i + 1, h));
else ret = max(ret, solve(i + 1, h, 0, 0) + ima(i + 1, h) + ima(i - 1, h));
}
}
} else {
if(!f1) {
for(int h = hp + 1; h <= n; ++h) {
ret = max(ret, solve(i + 1, h, 0, 0) + ima(i - 1, h) + ima(i + 1, h));
}
}
for(int h = hp; h >= 0; --h) {
if(h == 0) {
ret = max(ret, solve(i + 1, hp, 0, 1));
} else {
ret = max(ret, solve(i + 1, h, 1, 0) + ima(i + 1, h) - (h == hp) * ima(i, h));
}
}
}
return ret;
}
ll max_weights(int z, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
memset(dp, -1, sizeof dp);
x = a, y = b, w = c;
n = z, m = d;
return solve(0, 0, 0, 0);
}