oj.uz

Submission #29755

# Submission time Handle Problem Language Result Execution time Memory
29755 2017-07-20T14:14:59 Z osmanorhan Wombats (IOI13_wombats) C++14
100 / 100
 9856 ms 176744 KB 
#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];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 176744 KB Output is correct
2 Correct 9 ms 176744 KB Output is correct
3 Correct 99 ms 176744 KB Output is correct
4 Correct 9 ms 176744 KB Output is correct
5 Correct 3 ms 176744 KB Output is correct
6 Correct 0 ms 176744 KB Output is correct
7 Correct 3 ms 176744 KB Output is correct
8 Correct 3 ms 176744 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 176744 KB Output is correct
2 Correct 3 ms 176744 KB Output is correct
3 Correct 0 ms 176744 KB Output is correct
4 Correct 3 ms 176744 KB Output is correct
5 Correct 0 ms 176744 KB Output is correct
6 Correct 6 ms 176744 KB Output is correct
7 Correct 3 ms 176744 KB Output is correct
8 Correct 6 ms 176744 KB Output is correct
9 Correct 0 ms 176744 KB Output is correct
10 Correct 3 ms 176744 KB Output is correct
11 Correct 96 ms 176744 KB Output is correct
12 Correct 0 ms 176744 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 176744 KB Output is correct
2 Correct 199 ms 176744 KB Output is correct
3 Correct 203 ms 176744 KB Output is correct
4 Correct 213 ms 176744 KB Output is correct
5 Correct 249 ms 176744 KB Output is correct
6 Correct 0 ms 176744 KB Output is correct
7 Correct 3 ms 176744 KB Output is correct
8 Correct 6 ms 176744 KB Output is correct
9 Correct 1016 ms 176744 KB Output is correct
10 Correct 0 ms 176744 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 176744 KB Output is correct
2 Correct 9 ms 176744 KB Output is correct
3 Correct 9 ms 176744 KB Output is correct
4 Correct 53 ms 176744 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 176744 KB Output is correct
2 Correct 193 ms 176744 KB Output is correct
3 Correct 216 ms 176744 KB Output is correct
4 Correct 229 ms 176744 KB Output is correct
5 Correct 216 ms 176744 KB Output is correct
6 Correct 9 ms 176744 KB Output is correct
7 Correct 13 ms 176744 KB Output is correct
8 Correct 13 ms 176744 KB Output is correct
9 Correct 43 ms 176744 KB Output is correct
10 Correct 3 ms 176744 KB Output is correct
11 Correct 16 ms 176744 KB Output is correct
12 Correct 139 ms 176744 KB Output is correct
13 Correct 9 ms 176744 KB Output is correct
14 Correct 0 ms 176744 KB Output is correct
15 Correct 0 ms 176744 KB Output is correct
16 Correct 0 ms 176744 KB Output is correct
17 Correct 9 ms 176744 KB Output is correct
18 Correct 3 ms 176744 KB Output is correct
19 Correct 3 ms 176744 KB Output is correct
20 Correct 0 ms 176744 KB Output is correct
21 Correct 0 ms 176744 KB Output is correct
22 Correct 3 ms 176744 KB Output is correct
23 Correct 3 ms 176744 KB Output is correct
24 Correct 0 ms 176744 KB Output is correct
25 Correct 126 ms 176744 KB Output is correct
26 Correct 3 ms 176744 KB Output is correct
27 Correct 953 ms 176744 KB Output is correct
28 Correct 2003 ms 176744 KB Output is correct
29 Correct 2159 ms 176744 KB Output is correct
30 Correct 2023 ms 176744 KB Output is correct
31 Correct 2386 ms 176744 KB Output is correct
32 Correct 0 ms 176744 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 176744 KB Output is correct
2 Correct 233 ms 176744 KB Output is correct
3 Correct 233 ms 176744 KB Output is correct
4 Correct 216 ms 176744 KB Output is correct
5 Correct 223 ms 176744 KB Output is correct
6 Correct 9 ms 176744 KB Output is correct
7 Correct 3 ms 176744 KB Output is correct
8 Correct 9 ms 176744 KB Output is correct
9 Correct 59 ms 176744 KB Output is correct
10 Correct 3 ms 176744 KB Output is correct
11 Correct 13 ms 176744 KB Output is correct
12 Correct 93 ms 176744 KB Output is correct
13 Correct 6 ms 176744 KB Output is correct
14 Correct 6 ms 176744 KB Output is correct
15 Correct 2093 ms 176744 KB Output is correct
16 Correct 9856 ms 176744 KB Output is correct
17 Correct 0 ms 176744 KB Output is correct
18 Correct 3 ms 176744 KB Output is correct
19 Correct 0 ms 176744 KB Output is correct
20 Correct 0 ms 176744 KB Output is correct
21 Correct 3 ms 176744 KB Output is correct
22 Correct 0 ms 176744 KB Output is correct
23 Correct 3 ms 176744 KB Output is correct
24 Correct 6 ms 176744 KB Output is correct
25 Correct 3 ms 176744 KB Output is correct
26 Correct 3 ms 176744 KB Output is correct
27 Correct 103 ms 176744 KB Output is correct
28 Correct 3 ms 176744 KB Output is correct
29 Correct 956 ms 176744 KB Output is correct
30 Correct 2126 ms 176744 KB Output is correct
31 Correct 8138 ms 176744 KB Output is correct
32 Correct 9006 ms 176744 KB Output is correct
33 Correct 2109 ms 176744 KB Output is correct
34 Correct 9359 ms 176744 KB Output is correct
35 Correct 2059 ms 176744 KB Output is correct
36 Correct 9043 ms 176744 KB Output is correct
37 Correct 2403 ms 176744 KB Output is correct
38 Correct 8649 ms 176744 KB Output is correct
39 Correct 0 ms 176744 KB Output is correct
40 Correct 9716 ms 176744 KB Output is correct