제출 #962624

#제출 시각아이디문제언어결과실행 시간메모리
962624nguyentunglam웜뱃 (IOI13_wombats)C++17
0 / 100
1431 ms42640 KiB
#include<bits/stdc++.h> using namespace std; #include "wombats.h" const int M = 1000; int T[M + 10][200][200]; int h[5010][210], v[5010][210]; int f[210][210], opt[210][210]; int r, c; void calc (int l, int r) { for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) f[i][j] = (i == j ? 0 : 1e9); for(int row = l; row <= r; row++) { if (row != l) { for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) { f[i][j] += v[row - 1][j]; } } for(int i = 0; i < c; i++) { for(int j = 1; j < c; j++) f[i][j] = min(f[i][j], f[i][j - 1] + h[row][j - 1]); for(int j = c - 2; j >= 0; j--) f[i][j] = min(f[i][j], f[i][j + 1] + h[row][j]); } } } void up (int s, int l, int r, int pos) { // if (s == 2) cout << l << " " << r << endl; if (l == r) { calc(l, r); for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) T[s][i][j] = f[i][j]; return; } int mid = l + r >> 1; if (pos <= mid) up(s << 1, l, mid, pos); else up(s << 1 | 1, mid + 1, r, pos); // for(int i = 0; i < c; i++) { // T[s][i][i] = 2e9; // for(int j = 0; j < c; j++) { // int cost = T[s << 1][i][j] + v[mid][j] + T[s << 1 | 1][j][i]; // if (T[s][i][i] > cost) { // T[s][i][i] = cost; // opt[i][i] = j; // } // } // } for(int i = c - 1; i >= 0; i--) for(int j = 0; j < c; j++) { T[s][i][j] = 1e9; for(int k = 0; k < c; k++) { int cost = T[s << 1][i][k] + v[mid][k] + T[s << 1 | 1][k][j]; if (T[s][i][j] > cost) { T[s][i][j] = cost; opt[i][j] = k; } } } } 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 + 1 < c; j++) h[i][j] = H[i][j]; for(int i = 0; i + 1 < r; i++) for(int j = 0; j < c; j++) v[i][j] = V[i][j]; for(int i = 0; i < c; i++) up(1, 0, r - 1, i); // cout << T[2][2][1]; // exit(0); // for(int i = 0; i < r; i++) { // for(int j = 0; j + 1 < c; j++) cout << h[i][j] << " "; // cout << endl; // } // // for(int i = 0; i + 1 < r; i++) { // for(int j = 0; j < c; j++) cout << v[i][j] << " "; // cout << endl; // } } void changeH(int P, int Q, int W) { h[P][Q] = W; up(1, 0, r - 1, P); } void changeV(int P, int Q, int W) { v[P][Q] = W; up(1, 0, r - 1, P); } int escape(int V1, int V2) { return T[1][V1][V2]; } #ifdef ngu #define fail(s, x...) do { \ fprintf(stderr, s "\n", ## x); \ exit(1); \ } while(0) static int H[5000][200]; static int V[5000][200]; int main() { ofstream cout("task.out"); int R, C, E, P, Q, W, V1, V2, event, i, j; int res; FILE *f = fopen("task.inp", "r"); if (!f) fail("Failed to open input file."); res = fscanf(f, "%d%d", &R, &C); for (i = 0; i < R; ++i) for (j = 0; j < C-1; ++j) res = fscanf(f, "%d", &H[i][j]); for (i = 0; i < R-1; ++i) for (j = 0; j < C; ++j) res = fscanf(f, "%d", &V[i][j]); init(R, C, H, V); res = fscanf(f, "%d", &E); for (i = 0; i < E; i++) { res = fscanf(f, "%d", &event); if (event == 1) { res = fscanf(f, "%d%d%d", &P, &Q, &W); changeH(P, Q, W); } else if (event == 2) { res = fscanf(f, "%d%d%d", &P, &Q, &W); changeV(P, Q, W); } else if (event == 3) { res = fscanf(f, "%d%d", &V1, &V2); printf("%d\n", escape(V1, V2)); } else fail("Invalid event type."); } fclose(f); return 0; cout.close(); } #endif // ngu

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void up(int, int, int, int)':
wombats.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = l + r >> 1;
      |             ~~^~~
#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...