oj.uz

Submission #600267

# Submission time Handle Problem Language Result Execution time Memory
600267 2022-07-20T15:52:28 Z MilosMilutinovic Wombats (IOI13_wombats) C++14
76 / 100
 7957 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

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

const long long inf = 1e18;

int n, m, h[MAXR][MAXC], v[MAXR][MAXC], ls[MAXN], rs[MAXN], root, tsz;
long long 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];
      }
      long long 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];
        }
      }
    }
  }
}

long long 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 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 13012 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 89 ms 15700 KB Output is correct
4 Correct 7 ms 12992 KB Output is correct
5 Correct 6 ms 13012 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 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 440 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 520 KB Output is correct
11 Correct 89 ms 2788 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 687 ms 5820 KB Output is correct
2 Correct 637 ms 5836 KB Output is correct
3 Correct 647 ms 5816 KB Output is correct
4 Correct 642 ms 5812 KB Output is correct
5 Correct 633 ms 5772 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3039 ms 5816 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 22612 KB Output is correct
2 Correct 16 ms 22612 KB Output is correct
3 Correct 16 ms 22596 KB Output is correct
4 Correct 47 ms 23928 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 5812 KB Output is correct
2 Correct 610 ms 5760 KB Output is correct
3 Correct 654 ms 5836 KB Output is correct
4 Correct 662 ms 5812 KB Output is correct
5 Correct 618 ms 5768 KB Output is correct
6 Correct 11 ms 22740 KB Output is correct
7 Correct 11 ms 22612 KB Output is correct
8 Correct 12 ms 22612 KB Output is correct
9 Correct 44 ms 23924 KB Output is correct
10 Correct 6 ms 12992 KB Output is correct
11 Correct 6 ms 13020 KB Output is correct
12 Correct 88 ms 15680 KB Output is correct
13 Correct 6 ms 13012 KB Output is correct
14 Correct 9 ms 13012 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 444 KB Output is correct
20 Correct 1 ms 440 KB Output is correct
21 Correct 1 ms 444 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 81 ms 2824 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3165 ms 5836 KB Output is correct
28 Correct 7957 ms 188160 KB Output is correct
29 Correct 7657 ms 184940 KB Output is correct
30 Correct 7766 ms 184888 KB Output is correct
31 Correct 7936 ms 189772 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 5812 KB Output is correct
2 Correct 600 ms 5756 KB Output is correct
3 Correct 646 ms 5712 KB Output is correct
4 Correct 644 ms 5820 KB Output is correct
5 Correct 696 ms 5768 KB Output is correct
6 Correct 10 ms 22612 KB Output is correct
7 Correct 12 ms 22612 KB Output is correct
8 Correct 13 ms 22612 KB Output is correct
9 Correct 58 ms 24020 KB Output is correct
10 Correct 9 ms 13004 KB Output is correct
11 Correct 7 ms 12996 KB Output is correct
12 Correct 75 ms 15788 KB Output is correct
13 Correct 7 ms 12996 KB Output is correct
14 Correct 6 ms 13012 KB Output is correct
15 Runtime error 5507 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -