Submission #1263799

#TimeUsernameProblemLanguageResultExecution timeMemory
1263799repmannWombats (IOI13_wombats)C++20
55 / 100
20088 ms327680 KiB
#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][1000][200], BOTMEM[200][1000][200], DP[2][200]; int P[2501], I[5000]; inline void TopDP(int u, int row) { int start = -1; if(row >= 0) for(int i = row - 1; i >= 0; i--) if(I[i] >= 0) {start = i; break;} // cout << row << ' ' << start << '\n'; if(start < 0) { DP[0][u] = 0; for(int i = u - 1; i >= 0; i--) DP[0][i] = DP[0][i + 1] + H[0][i]; for(int i = u + 1; i < C; i++) DP[0][i] = DP[0][i - 1] + H[0][i - 1]; if(I[0] >= 0) __builtin_memcpy(TOPMEM[u][I[0]], DP[0], C << 2); start = 0; } else __builtin_memcpy(DP[0], TOPMEM[u][I[start]], C << 2); for(int i = start + 1; 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(I[i] >= 0) { bool flag = (i <= row) || (row < 0); for(int j = 0; (j < C) && !flag; j++) flag = TOPMEM[u][I[i]][j] != DP[1][j]; if(!flag) return; else __builtin_memcpy(TOPMEM[u][I[i]], DP[1], C << 2); __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) { int start = -1; if(row >= 0) for(int i = row + 1; i < R; i++) if(I[i] >= 0) {start = i; break;} // cout << row << ' ' << start << '\n'; if(start < 0) { DP[0][v] = 0; for(int i = v - 1; i >= 0; i--) DP[0][i] = DP[0][i + 1] + H[R - 1][i]; for(int i = v + 1; i < C; i++) DP[0][i] = DP[0][i - 1] + H[R - 1][i - 1]; if(I[R - 1] >= 0) __builtin_memcpy(BOTMEM[v][I[R - 1]], DP[0], C << 2); start = R - 1; } else __builtin_memcpy(DP[0], BOTMEM[v][I[start]], C << 2); for(int i = start - 1; 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(I[i] >= 0) { bool flag = (i >= row) || (row < 0); for(int j = 0; (j < C) && !flag; j++) flag = BOTMEM[v][I[i]][j] != DP[1][j]; if(!flag) return; else __builtin_memcpy(BOTMEM[v][I[i]], DP[1], C << 2); __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; i < R; i++) I[i] = -1; for(int i = 0; i <= (R >> 1); i++) P[i] = i; random_shuffle(P, P + (R >> 1) + 1); // for(int i = 0; i <= min(999, R >> 1); i++) cout << P[i] << " \n"[i == min(999, R >> 1)]; for(int i = 0; i <= min(999, R >> 1); i++) I[P[i]] = i; for(int i = (R >> 1) + 1; i < R; i++) P[i - (R >> 1) - 1] = i; random_shuffle(P, P + R - (R >> 1)); // for(int i = 0; i <= min(999, R - (R >> 1) - 2); i++) cout << P[i] << " \n"[i == min(999, R - (R >> 1) - 2)]; for(int i = 0; i <= min(999, R - (R >> 1) - 2); i++) I[P[i]] = i; // cout << "I:\n"; // for(int i = 0; i < R; i++) cout << I[i] << " \n"[i == (R - 1)]; // cout << "PREV:\n"; // for(int i = 0; i < R; i++) cout << PREV[i] << " \n"[i == (R - 1)]; for(int i = 0; i < C; i++) TopDP(i, -1); for(int i = 0; i < C; i++) BotDP(i, -1); return; } void changeH(int r, int c, int w) { H[r][c] = w; if(r <= (R >> 1)) for(int i = 0; i < C; i++) TopDP(i, -1); else for(int i = 0; i < C; i++) BotDP(i, r); return; } void changeV(int r, int c, int w) { V[r][c] = w; if(r < (R >> 1)) for(int i = 0; i < C; i++) TopDP(i, -1); else if(r > (R >> 1)) for(int i = 0; i < C; i++) BotDP(i, r); return; } int escape(int u, int v) { int ret = INT_MAX; 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 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...