Submission #1260530

#TimeUsernameProblemLanguageResultExecution timeMemory
1260530repmannWombats (IOI13_wombats)C++20
55 / 100
20091 ms20784 KiB
#include <bits/stdc++.h> #include "wombats.h" using namespace std; int R, C; int cnt, sz, LRU[200], I[200]; int H[5000][200], V[5000][200], DP[50][5000][200]; int temp[200]; inline void doDP(int u, int row = 0) { int index = I[u]; if(!row) { DP[index][0][u] = 0; for(int i = u - 1; i >= 0; i--) DP[index][0][i] = DP[index][0][i + 1] + H[0][i]; if(u < (C - 1)) for(int i = u + 1; i < C; i++) DP[index][0][i] = DP[index][0][i - 1] + H[0][i - 1]; } for(int i = row + !row; i < R; i++) { temp[0] = DP[index][i - 1][0] + V[i - 1][0]; for(int j = 1; j < C; j++) { temp[j] = min(temp[j - 1] + H[i][j - 1], DP[index][i - 1][j] + V[i - 1][j]); } int dp = DP[index][i - 1][C - 1] + V[i - 1][C - 1]; for(int j = C - 2; j >= 0; j--) { dp = min(dp + H[i][j], DP[index][i - 1][j] + V[i - 1][j]); temp[j] = min(dp, temp[j]); } bool diff = false; for(int j = 0; j < C; j++) if(temp[j] != DP[index][i][j]) {diff = true; break;} if(!diff) break; for(int j = 0; j < C; j++) DP[index][i][j] = temp[j]; } 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 < C; i++) I[i] = -1; return; } void changeH(int r, int c, int w) { H[r][c] = w; for(int i = 0; i < C; i++) if(I[i] >= 0) doDP(i, r); return; } void changeV(int r, int c, int w) { V[r][c] = w; for(int i = 0; i < C; i++) if(I[i] >= 0) doDP(i, r + 1); return; } int escape(int u, int v) { if(I[u] < 0) { if(sz < 1) I[u] = sz++; else { int kick = -1; for(int i = 0; i < C; i++) if((I[i] >= 0) && ((kick < 0) || (LRU[i] < LRU[kick]))) kick = i; I[u] = I[kick]; I[kick] = -1; } doDP(u); } LRU[u] = ++cnt; return DP[I[u]][R - 1][v]; } //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...