# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
763402 | SanguineChameleon | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e3 + 20;
const int maxM = 2e2 + 20;
int hor[5020][220];
int ver[5020][220];
int memo[220][220];
int tmp[5020][220];
int dp[5020][220];
int N, M;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
N = R;
M = C;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M - 1; j++) {
hor[i][j] = H[i][j];
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M; j++) {
ver[i][j] = V[i][j];
}
}
calc(-1);
}
void changeH(int P, int Q, int W) {
hor[P][Q] = W;
calc(-1);
}
void changeV(int P, int Q, int W) {
ver[P][Q] = W;
calc(-1);
}
void calc(int X) {
for (X = 0; X < M; X++) {
dp[0][X] = 0;
for (int i = X - 1; i >= 0; i--) {
dp[0][i] = dp[0][i + 1] + hor[0][i];
}
for (int i = X + 1; i < M; i++) {
dp[0][i] = dp[0][i - 1] + hor[0][i - 1];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++) {
tmp[i][j] = dp[i - 1][j] + ver[i - 1][j];
dp[i][j] = tmp[i][j];
}
int best = tmp[i][0];
for (int j = 1; j < M; j++) {
best = min(best + hor[i][j - 1], tmp[i][j]);
dp[i][j] = min(dp[i][j], best);
}
best = tmp[i][M - 1];
for (int j = M - 2; j >= 0; j--) {
best = min(best + hor[i][j], tmp[i][j]);
dp[i][j] = min(dp[i][j], best);
}
}
for (int i = 0; i < M; i++) {
memo[X][i] = dp[N - 1][i];
}
}
}
int escape(int V1, int V2) {
return memo[V1][V2];
}