oj.uz

Submission #600270

# Submission time Handle Problem Language Result Execution time Memory
600270 2022-07-20T15:57:54 Z MilosMilutinovic Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 194248 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];

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++) {
      for (int k = 0; k < m; k++) {
        dp[c][i][j] = min(dp[c][i][j], dp[ls[c]][i][k] + dp[rs[c]][k][j] + v[mid][k]); // optimize this
      }
    }
  }
}

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:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void build(int&, int, int)':
wombats.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   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 71 ms 14272 KB Output is correct
4 Correct 6 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 0 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 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 62 ms 1344 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 589 ms 3256 KB Output is correct
2 Correct 549 ms 3228 KB Output is correct
3 Correct 604 ms 3248 KB Output is correct
4 Correct 603 ms 3252 KB Output is correct
5 Correct 559 ms 3232 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
9 Correct 2856 ms 3252 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 10 ms 21412 KB Output is correct
2 Correct 10 ms 21332 KB Output is correct
3 Correct 10 ms 21424 KB Output is correct
4 Correct 42 ms 22184 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 3256 KB Output is correct
2 Correct 548 ms 3296 KB Output is correct
3 Correct 588 ms 3252 KB Output is correct
4 Correct 584 ms 3248 KB Output is correct
5 Correct 552 ms 3232 KB Output is correct
6 Correct 12 ms 21332 KB Output is correct
7 Correct 11 ms 21332 KB Output is correct
8 Correct 11 ms 21428 KB Output is correct
9 Correct 43 ms 22192 KB Output is correct
10 Correct 6 ms 12628 KB Output is correct
11 Correct 6 ms 12628 KB Output is correct
12 Correct 70 ms 14244 KB Output is correct
13 Correct 6 ms 12756 KB Output is correct
14 Correct 6 ms 12680 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 340 KB Output is correct
20 Correct 1 ms 340 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 340 KB Output is correct
25 Correct 68 ms 1336 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2718 ms 3256 KB Output is correct
28 Correct 7091 ms 102620 KB Output is correct
29 Correct 6878 ms 99616 KB Output is correct
30 Correct 6949 ms 99608 KB Output is correct
31 Correct 7055 ms 103468 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 3276 KB Output is correct
2 Correct 570 ms 3276 KB Output is correct
3 Correct 586 ms 3380 KB Output is correct
4 Correct 584 ms 3256 KB Output is correct
5 Correct 554 ms 3228 KB Output is correct
6 Correct 10 ms 21424 KB Output is correct
7 Correct 10 ms 21356 KB Output is correct
8 Correct 10 ms 21332 KB Output is correct
9 Correct 41 ms 22104 KB Output is correct
10 Correct 6 ms 12628 KB Output is correct
11 Correct 6 ms 12628 KB Output is correct
12 Correct 70 ms 14248 KB Output is correct
13 Correct 7 ms 12628 KB Output is correct
14 Correct 6 ms 12628 KB Output is correct
15 Correct 6583 ms 194248 KB Output is correct
16 Execution timed out 20071 ms 193404 KB Time limit exceeded
17 Halted 0 ms 0 KB -