oj.uz

Submission #600282

# Submission time Handle Problem Language Result Execution time Memory
600282 2022-07-20T16:16:56 Z MilosMilutinovic Wombats (IOI13_wombats) C++14
100 / 100
 3941 ms 193572 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXR = 5005;
const int MAXC = 205;
const int MAXN = 3005;

const int inf = 1e9;

int n, m, h[MAXR][MAXC], v[MAXR][MAXC], ls[MAXN], rs[MAXN], root, tsz;
int dp[MAXN][MAXC][MAXC], pref[MAXC];

void buildSmall(int c, int l, int r) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      dp[c][i][j] = (i == j ? 0LL : inf);
    }
  }
  for (int i = l; i <= r; i++) {
    for (int x = 0; x < m; x++) {
      pref[0] = 0;
      for (int j = 1; j < m; j++) {
        pref[j] = pref[j - 1] + h[i][j - 1];
      }
      int mn = 1e18;
      for (int j = 0; j < m; j++) {
        mn = min(mn, dp[c][x][j] - pref[j]);
        dp[c][x][j] = min(dp[c][x][j], mn + pref[j]);
      }
      mn = 1e18;
      for (int j = m - 1; j >= 0; j--) {
        mn = min(mn, dp[c][x][j] + pref[j]);
        dp[c][x][j] = min(dp[c][x][j], mn - pref[j]);
      }
      if (i < r) {
        for (int j = 0; j < m; j++) {
          dp[c][x][j] += v[i][j];
        }
      }
    }
  }
}

int up[MAXR], down[MAXR];
int opt[MAXC][MAXC];

void pull(int c, int l, int r) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      dp[c][i][j] = inf;
    }
  }
  int mid = l + r >> 1;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      if (dp[ls[c]][i][j] + v[mid][j] + dp[rs[c]][j][i] < dp[c][i][i]) {
        dp[c][i][i] = dp[ls[c]][i][j] + v[mid][j] + dp[rs[c]][j][i];
        opt[i][i] = j;
      }
    }
  }
  for (int d = 1; d < m; d++) {
    for (int i = 0; i < m; i++) {
      if (i + d < m) {
        int j = i + d;
        for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
          if (dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j] < dp[c][i][j]) {
            dp[c][i][j] = dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j];
            opt[i][j] = k;
          }
        }
      }
      if (i >= d) {
        int j = i - d;
        for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
          if (dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j] < dp[c][i][j]) {
            dp[c][i][j] = dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j];
            opt[i][j] = k;
          }
        }
      }
    }
  }
}

void build(int& c, int l, int r) {
  if (!c) c = ++tsz;
  if (r - l <= 10) {
    buildSmall(c, l, r);
    return;
  }
  int mid = l + r >> 1;
  build(ls[c], l, mid);
  build(rs[c], mid + 1, r);
  pull(c, l, r);
}

void update(int c, int l, int r, int i) {
  if (r - l <= 10) {
    buildSmall(c, l, r);
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    update(ls[c], l, mid, i);
  } else {
    update(rs[c], mid + 1, r, i);
  }
  pull(c, l, r);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  n = R;
  m = C;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m - 1; j++) {
      h[i][j] = H[i][j];
    }
  }
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < m; j++) {
      v[i][j] = V[i][j];
    }
  }
  build(root, 0, n - 1);
}

void changeH(int P, int Q, int W) {
  h[P][Q] = W;
  update(root, 0, n - 1, P);
}

void changeV(int P, int Q, int W) {
  v[P][Q] = W;
  update(root, 0, n - 1, P);
}

int escape(int V1, int V2) {
  return dp[root][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]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void buildSmall(int, int, int)':
wombats.cpp:27:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |       int mn = 1e18;
      |                ^~~~
wombats.cpp:32:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   32 |       mn = 1e18;
      |            ^~~~
wombats.cpp: In function 'void pull(int, int, int)':
wombats.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void build(int&, int, int)':
wombats.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:105:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 7 ms 12628 KB Output is correct
3 Correct 68 ms 14268 KB Output is correct
4 Correct 7 ms 12628 KB Output is correct
5 Correct 6 ms 12628 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3284 KB Output is correct
2 Correct 68 ms 3316 KB Output is correct
3 Correct 82 ms 3336 KB Output is correct
4 Correct 91 ms 3336 KB Output is correct
5 Correct 91 ms 3332 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 302 ms 3284 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21332 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21332 KB Output is correct
4 Correct 47 ms 22140 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3352 KB Output is correct
2 Correct 74 ms 3212 KB Output is correct
3 Correct 82 ms 3336 KB Output is correct
4 Correct 86 ms 3340 KB Output is correct
5 Correct 87 ms 3320 KB Output is correct
6 Correct 11 ms 21420 KB Output is correct
7 Correct 12 ms 21332 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 44 ms 22220 KB Output is correct
10 Correct 6 ms 12628 KB Output is correct
11 Correct 6 ms 12692 KB Output is correct
12 Correct 69 ms 14208 KB Output is correct
13 Correct 6 ms 12628 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 392 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 65 ms 1372 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 302 ms 3356 KB Output is correct
28 Correct 919 ms 102628 KB Output is correct
29 Correct 941 ms 99680 KB Output is correct
30 Correct 1008 ms 99764 KB Output is correct
31 Correct 993 ms 103528 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3340 KB Output is correct
2 Correct 69 ms 3316 KB Output is correct
3 Correct 91 ms 3340 KB Output is correct
4 Correct 86 ms 3344 KB Output is correct
5 Correct 82 ms 3320 KB Output is correct
6 Correct 11 ms 21312 KB Output is correct
7 Correct 12 ms 21332 KB Output is correct
8 Correct 12 ms 21332 KB Output is correct
9 Correct 42 ms 22100 KB Output is correct
10 Correct 7 ms 12628 KB Output is correct
11 Correct 6 ms 12628 KB Output is correct
12 Correct 67 ms 14260 KB Output is correct
13 Correct 6 ms 12628 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 1188 ms 184608 KB Output is correct
16 Correct 3941 ms 187328 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 70 ms 2832 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 296 ms 3520 KB Output is correct
30 Correct 947 ms 106296 KB Output is correct
31 Correct 3352 ms 192968 KB Output is correct
32 Correct 3333 ms 192928 KB Output is correct
33 Correct 967 ms 103332 KB Output is correct
34 Correct 3523 ms 189636 KB Output is correct
35 Correct 998 ms 103136 KB Output is correct
36 Correct 3578 ms 189576 KB Output is correct
37 Correct 986 ms 108096 KB Output is correct
38 Correct 3399 ms 193572 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3738 ms 189608 KB Output is correct