# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
763402 | 2023-06-22T09:18:51 Z | SanguineChameleon | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KB |
#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]; }