답안 #2622 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2622	2013-07-28T03:12:46 Z	model_code	웜뱃 (IOI13_wombats)	C++	100 / 100	10688 ms	176712 KB

wombats

#include "wombats.h"
 
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define K 15
#define INF 5000010
 
int R, C;
int H[5000][200];
int V[5000][200];
 
int T[1024][200][200];
 
static void hsmooth(int* A, int r) {
  for(int i = 1; i < C; i++) {
    A[i] = min(A[i], A[i - 1] + H[r][i - 1]);
  }
  for(int i = C - 2; i >= 0; i--) {
    A[i] = min(A[i], A[i + 1] + H[r][i]);
  }
}
 
static void compute_base(int A[200][200], int rlo, int rhi) {
  for(int i = 0; i < C; i++) {
    int* B = A[i];
    for(int j = 0; j < C; j++) {
      B[j] = i == j ? 0 : INF;
    }
 
    for(int r = rlo; r < rhi; r++) {
      hsmooth(B, r);
      for(int j = 0; j < C; j++) {
        B[j] += V[r][j];
      }
    }
  }
}
 
static void solve(int i, int jlo, int jhi, int klo, int khi,
                  int R[200], int X[200], int Y[200][200]) {
  if(jlo == jhi) {
    return;
  }
 
  int jmd = (jlo + jhi) / 2;
  int kmd = klo;
 
  R[jmd] = X[kmd] + Y[kmd][jmd];
  for(int k = klo + 1; k < khi; k++) {
    int v = X[k] + Y[k][jmd];
    if(v < R[jmd]) {
      R[jmd] = v;
      kmd = k;
    }
  }
 
  solve(i, jlo, jmd, klo, kmd + 1, R, X, Y);
  solve(i, jmd + 1, jhi, kmd, khi, R, X, Y);
}
 
static void compute_merge(int R[200][200], int X[200][200], int Y[200][200]) {
  for(int i = 0; i < C; i++) {
    solve(i, 0, C, 0, C, R[i], X[i], Y);
  }
}
 
static void update(int x, int rlo, int rhi, int rupdate) {
  if(rlo + 1 >= R) {
  } else if(rhi - rlo == K) {
    compute_base(T[x], rlo, min(R - 1, rhi));
  } else {
    int rmd = (rlo + rhi) / 2;
    if(rupdate == -1 || rupdate < rmd) {
      update(2 * x + 1, rlo, rmd, rupdate);
    }
    if(rupdate == -1 || rmd <= rupdate) {
      update(2 * x + 2, rmd, rhi, rupdate);
    }
    if(rmd + 1 < R) {
      compute_merge(T[x], T[2 * x + 1], T[2 * x + 2]);
    } else {
      memcpy(T[x], T[2 * x + 1], sizeof(T[x]));
    }
  }
}
 
void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) {
  R = RR;
  C = CC;
  memcpy(H, HH, sizeof(H));
  memcpy(V, VV, sizeof(V));
  update(0, 0, 512 * K, -1);
}
 
void changeH(int P, int Q, int W) {
  H[P][Q] = W;
  update(0, 0, 512 * K, P);
}
 
void changeV(int P, int Q, int W) {
  V[P][Q] = W;
  update(0, 0, 512 * K, P);
}
 
int escape(int V1, int V2) {
  hsmooth(T[0][V1], R - 1);
  return T[0][V1][V2];
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	176712 KB	Output is correct
2	Correct	8 ms	176712 KB	Output is correct
3	Correct	100 ms	176712 KB	Output is correct
4	Correct	8 ms	176712 KB	Output is correct
5	Correct	8 ms	176712 KB	Output is correct
6	Correct	0 ms	176712 KB	Output is correct
7	Correct	8 ms	176712 KB	Output is correct
8	Correct	0 ms	176712 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	176712 KB	Output is correct
2	Correct	4 ms	176712 KB	Output is correct
3	Correct	0 ms	176712 KB	Output is correct
4	Correct	8 ms	176712 KB	Output is correct
5	Correct	4 ms	176712 KB	Output is correct
6	Correct	0 ms	176712 KB	Output is correct
7	Correct	8 ms	176712 KB	Output is correct
8	Correct	4 ms	176712 KB	Output is correct
9	Correct	4 ms	176712 KB	Output is correct
10	Correct	4 ms	176712 KB	Output is correct
11	Correct	132 ms	176712 KB	Output is correct
12	Correct	4 ms	176712 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	228 ms	176712 KB	Output is correct
2	Correct	232 ms	176712 KB	Output is correct
3	Correct	244 ms	176712 KB	Output is correct
4	Correct	252 ms	176712 KB	Output is correct
5	Correct	252 ms	176712 KB	Output is correct
6	Correct	8 ms	176712 KB	Output is correct
7	Correct	0 ms	176712 KB	Output is correct
8	Correct	8 ms	176712 KB	Output is correct
9	Correct	1152 ms	176712 KB	Output is correct
10	Correct	4 ms	176712 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	176712 KB	Output is correct
2	Correct	8 ms	176712 KB	Output is correct
3	Correct	12 ms	176712 KB	Output is correct
4	Correct	40 ms	176712 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	228 ms	176712 KB	Output is correct
2	Correct	228 ms	176712 KB	Output is correct
3	Correct	244 ms	176712 KB	Output is correct
4	Correct	252 ms	176712 KB	Output is correct
5	Correct	252 ms	176712 KB	Output is correct
6	Correct	12 ms	176712 KB	Output is correct
7	Correct	4 ms	176712 KB	Output is correct
8	Correct	4 ms	176712 KB	Output is correct
9	Correct	48 ms	176712 KB	Output is correct
10	Correct	0 ms	176712 KB	Output is correct
11	Correct	4 ms	176712 KB	Output is correct
12	Correct	100 ms	176712 KB	Output is correct
13	Correct	4 ms	176712 KB	Output is correct
14	Correct	4 ms	176712 KB	Output is correct
15	Correct	0 ms	176712 KB	Output is correct
16	Correct	4 ms	176712 KB	Output is correct
17	Correct	0 ms	176712 KB	Output is correct
18	Correct	4 ms	176712 KB	Output is correct
19	Correct	4 ms	176712 KB	Output is correct
20	Correct	0 ms	176712 KB	Output is correct
21	Correct	8 ms	176712 KB	Output is correct
22	Correct	0 ms	176712 KB	Output is correct
23	Correct	8 ms	176712 KB	Output is correct
24	Correct	0 ms	176712 KB	Output is correct
25	Correct	128 ms	176712 KB	Output is correct
26	Correct	4 ms	176712 KB	Output is correct
27	Correct	1156 ms	176712 KB	Output is correct
28	Correct	2356 ms	176712 KB	Output is correct
29	Correct	2468 ms	176712 KB	Output is correct
30	Correct	2448 ms	176712 KB	Output is correct
31	Correct	2744 ms	176712 KB	Output is correct
32	Correct	0 ms	176712 KB	Output is correct

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	228 ms	176712 KB	Output is correct
2	Correct	232 ms	176712 KB	Output is correct
3	Correct	244 ms	176712 KB	Output is correct
4	Correct	256 ms	176712 KB	Output is correct
5	Correct	248 ms	176712 KB	Output is correct
6	Correct	8 ms	176712 KB	Output is correct
7	Correct	4 ms	176712 KB	Output is correct
8	Correct	4 ms	176712 KB	Output is correct
9	Correct	48 ms	176712 KB	Output is correct
10	Correct	0 ms	176712 KB	Output is correct
11	Correct	8 ms	176712 KB	Output is correct
12	Correct	88 ms	176712 KB	Output is correct
13	Correct	0 ms	176712 KB	Output is correct
14	Correct	4 ms	176712 KB	Output is correct
15	Correct	2708 ms	176712 KB	Output is correct
16	Correct	10652 ms	176712 KB	Output is correct
17	Correct	4 ms	176712 KB	Output is correct
18	Correct	8 ms	176712 KB	Output is correct
19	Correct	4 ms	176712 KB	Output is correct
20	Correct	8 ms	176712 KB	Output is correct
21	Correct	4 ms	176712 KB	Output is correct
22	Correct	4 ms	176712 KB	Output is correct
23	Correct	4 ms	176712 KB	Output is correct
24	Correct	0 ms	176712 KB	Output is correct
25	Correct	4 ms	176712 KB	Output is correct
26	Correct	4 ms	176712 KB	Output is correct
27	Correct	124 ms	176712 KB	Output is correct
28	Correct	8 ms	176712 KB	Output is correct
29	Correct	1156 ms	176712 KB	Output is correct
30	Correct	2336 ms	176712 KB	Output is correct
31	Correct	9448 ms	176712 KB	Output is correct
32	Correct	10088 ms	176712 KB	Output is correct
33	Correct	2464 ms	176712 KB	Output is correct
34	Correct	10108 ms	176712 KB	Output is correct
35	Correct	2444 ms	176712 KB	Output is correct
36	Correct	9924 ms	176712 KB	Output is correct
37	Correct	2756 ms	176712 KB	Output is correct
38	Correct	10340 ms	176712 KB	Output is correct
39	Correct	4 ms	176712 KB	Output is correct
40	Correct	10688 ms	176712 KB	Output is correct

답안 #2622

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 24.0 / 24.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
24.0 / 24.0