#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
int R, C;
int H[5000][200], V[5000][200];
int TOP[200][200], BOT[200][200], TOPMEM[200][1252][200], BOTMEM[200][1252][200], DP[2][200];
int PREV[5000], I[5000];
int cnt, P[500], LT[200], LB[200];
inline void TopDP(int u, int row = 0)
{
if(!row)
{
DP[0][u] = 0;
for(int i = u - 1; i >= 0; i--) DP[0][i] = DP[0][i + 1] + H[0][i];
if(u < (C - 1)) for(int i = u + 1; i < C; i++) DP[0][i] = DP[0][i - 1] + H[0][i - 1];
}
for(int i = row + !row; i <= (R >> 1); i++)
{
DP[1][0] = DP[0][0] + V[i - 1][0];
for(int j = 1; j < C; j++) DP[1][j] = min(DP[1][j - 1] + H[i][j - 1], DP[0][j] + V[i - 1][j]);
int dp = DP[0][C - 1] + V[i - 1][C - 1];
DP[1][C - 1] = min(dp, DP[1][C - 1]);
for(int j = C - 2; j >= 0; j--)
{
dp = min(dp + H[i][j], DP[0][j] + V[i - 1][j]);
DP[1][j] = min(dp, DP[1][j]);
}
if(PREV[i] == i)
{
bool flag = false;
for(int j = 0; j < C; j++) if(TOPMEM[u][I[i]][j] != DP[1][j]) {flag = true; break;}
if(!flag) break;
else __builtin_memcpy(TOPMEM[u][I[i]], DP[1], C << 2);
}
__builtin_memcpy(DP[0], DP[1], C << 2);
}
for(int i = 0; i < C; i++) TOP[u][i] = DP[0][i];
return;
}
inline void BotDP(int v, int row = R - 1)
{
if(row == (R - 1))
{
DP[0][v] = 0;
for(int i = v - 1; i >= 0; i--) DP[0][i] = DP[0][i + 1] + H[R - 1][i];
if(v < (C - 1)) for(int i = v + 1; i < C; i++) DP[0][i] = DP[0][i - 1] + H[R - 1][i - 1];
}
for(int i = row - (row == (R - 2)); i > (R >> 1); i--)
{
DP[1][0] = DP[0][0] + V[i][0];
for(int j = 1; j < C; j++) DP[1][j] = min(DP[1][j - 1] + H[i][j - 1], DP[0][j] + V[i][j]);
int dp = DP[0][C - 1] + V[i][C - 1];
DP[1][C - 1] = min(dp, DP[1][C - 1]);
for(int j = C - 2; j >= 0; j--)
{
dp = min(dp + H[i][j], DP[0][j] + V[i][j]);
DP[1][j] = min(dp, DP[1][j]);
}
if(PREV[i] == i)
{
bool flag = false;
for(int j = 0; j < C; j++) if(BOTMEM[v][I[i]][j] != DP[1][j]) {flag = true; break;}
if(!flag) break;
else __builtin_memcpy(BOTMEM[v][I[i]], DP[1], C << 2);
}
__builtin_memcpy(DP[0], DP[1], C << 2);
}
for(int i = 0; i < C; i++) BOT[v][i] = DP[0][i];
return;
}
void init(int r, int c, int h[5000][200], int v[5000][200])
{
R = r;
C = c;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++) {H[i][j] = h[i][j]; V[i][j] = v[i][j];}
}
for(int i = 0, j = 0; i <= (R >> 1); i += 2)
{
I[i] = j++;
PREV[i] = i;
if(i < (R >> 1)) PREV[i + 1] = i;
}
for(int i = R - 1, j = 0; i > (R >> 1); i -= 2)
{
I[i] = j++;
PREV[i] = i;
if(i > ((R >> 1) + 1)) PREV[i - 1] = i;
}
// cout << "PREV:\n";
// for(int i = 0; i < R; i++) cout << PREV[i] << " \n"[i == (R - 1)];
// cout << "I:\n";
// for(int i = 0; i < R; i++) cout << I[i] << " \n"[i == (R - 1)];
for(int i = 0; i < C; i++) TopDP(i);
for(int i = 0; i < C; i++) BotDP(i);
return;
}
void changeH(int r, int c, int w)
{
H[r][c] = w;
P[cnt++] = PREV[r - (r == (R >> 1))];
return;
}
void changeV(int r, int c, int w)
{
V[r][c] = w;
P[cnt++] = PREV[r];
return;
}
int escape(int u, int v)
{
int ret = INT_MAX;
int mn = INT_MAX, mx = 0;
for(int i = LT[u]; i < cnt; i++) mn = min(P[i], mn);
if(mn < (R >> 1)) TopDP(u, mn);
LT[u] = cnt;
for(int i = LB[v]; i < cnt; i++) mx = max(P[i], mx);
if(mx > (R >> 1)) BotDP(v, mx);
LB[v] = cnt;
// cout << mn << ' ' << mx << '\n';
for(int i = 0; i < C; i++) ret = min(TOP[u][i] + V[R >> 1][i] + BOT[v][i], ret);
return ret;
}
//int h[5000][200], v[5000][200];
//int main()
//{
// ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int r, c;
// cin >> r >> c;
// for(int i = 0; i < r; i++)
// {
// for(int j = 0; j < (c - 1); j++) cin >> h[i][j];
// }
// for(int i = 0; i < (r - 1); i++)
// {
// for(int j = 0; j < c; j++) cin >> v[i][j];
// }
// init(r, c, h, v);
// int Q, t, u, v, w;
// cin >> Q;
// while(Q--)
// {
// cin >> t >> u >> v;
// if(t == 3) cout << escape(u, v) << '\n';
// else
// {
// cin >> w;
// if(t == 1) changeH(u, v, w);
// else changeV(u, v, w);
// }
// }
// return 0;
//}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |