oj.uz

Submission #516426

# Submission time Handle Problem Language Result Execution time Memory
516426 2022-01-21T09:59:43 Z 600Mihnea Wombats (IOI13_wombats) C++17
55 / 100
 314 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5000 + 7;
const int M = 200 + 7;
const int INF = (int) 1e9 + 7;
const int BUCKETSIZE = 1;
int H[N][M];
int V[N][M];

int n;
int m;

struct Node {
  int l;
  int r;
  vector<vector<int>> cost;
  Node() :
    l(0),
    r(0),
    cost(m, vector<int> (m, INF)) {
  }
};

vector<Node> tree;

void placeSmall(Node &guy, int l, int r) {
  assert(l <= r);
  guy.l = l;
  guy.r = r;
  for (int start = 0; start < m; start++) {
    for (int col = 0; col < m; col++) {
      guy.cost[start][col] = INF;
    }
    guy.cost[start][start] = 0;
    for (int col = 1; col < m; col++) {
      guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col - 1] + H[l][col - 1]);
    }
    for (int col = m - 2; col >= 0; col--){
      guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col + 1] + H[l][col]);
    }
  }
  for (int row = l + 1; row <= r; row++) {
    /// add row j
    for (int start = 0; start < m; start++) {
      for (int col = 0; col < m; col++) {
        guy.cost[start][col] += V[row - 1][col];
      }
      for (int col = 1; col < m; col++) {
        guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col - 1] + H[row][col - 1]);
      }
      for (int col = m - 2; col >= 0; col--){
        guy.cost[start][col] = min(guy.cost[start][col], guy.cost[start][col + 1] + H[row][col]);
      }
    }
  }
}

int A[M][M];
int B[M][M];
int opt[M][M];


void join(Node& solution, Node& lft, Node& rgh) {
  assert(lft.r + 1 == rgh.l);
  solution.l = lft.l;
  solution.r = rgh.r;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      A[i][j] = lft.cost[i][j] + V[lft.r][j];
      B[i][j] = rgh.cost[i][j];
      solution.cost[i][j] = INF;
      opt[i][j] = -1;
    }
  }
  for (int i = 0; i < m; i++) {
    for (int k = m - 1; k >= 0; k--) {
      int nd = m - 1, st = 0;
      if (k + 1 < m) {
        nd = opt[i][k + 1];
      }
      if (i - 1 >= 0) {
        st = opt[i - 1][k];
      }
      assert(st != -1);
      assert(nd != -1);
      for (int j = st; j <= nd; j++) {
        if (A[i][j] + B[j][k] < solution.cost[i][k]) {
          solution.cost[i][k] = A[i][j] + B[j][k];
          opt[i][k] = j;
        }
      }
    }
  }
}



void update(int v, int tl, int tr, int pos) {
  if (tr < pos || pos < tl) assert(0);
  int LEN = tr - tl + 1;
  if (LEN <= BUCKETSIZE) {
    placeSmall(tree[v], tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm) {
    update(2 * v, tl, tm, pos);
  } else {
    update(2 * v + 1, tm + 1, tr, pos);
  }
  join(tree[v], tree[2 * v], tree[2 * v + 1]);

}

void build(int v, int tl, int tr) {
  while (v >= (int) tree.size()) tree.push_back({});
  assert(v < (int) tree.size());
  if (tr - tl + 1 <= BUCKETSIZE) {

    placeSmall(tree[v], tl, tr);

    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm);
  build(2 * v + 1, tm + 1, tr);
  join(tree[v], tree[2 * v], tree[2 * v + 1]);
}


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

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

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

int escape(int V1, int V2) {
  return tree[1].cost[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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13764 KB Output is correct
2 Correct 8 ms 13764 KB Output is correct
3 Correct 74 ms 15464 KB Output is correct
4 Correct 9 ms 13836 KB Output is correct
5 Correct 8 ms 13764 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11824 KB Output is correct
2 Correct 66 ms 11724 KB Output is correct
3 Correct 87 ms 11828 KB Output is correct
4 Correct 84 ms 11824 KB Output is correct
5 Correct 98 ms 11724 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 314 ms 11832 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18756 KB Output is correct
2 Correct 12 ms 18756 KB Output is correct
3 Correct 12 ms 18756 KB Output is correct
4 Correct 45 ms 19540 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 11820 KB Output is correct
2 Correct 67 ms 11708 KB Output is correct
3 Correct 84 ms 11956 KB Output is correct
4 Correct 84 ms 11828 KB Output is correct
5 Correct 78 ms 11724 KB Output is correct
6 Correct 12 ms 18756 KB Output is correct
7 Correct 12 ms 18760 KB Output is correct
8 Correct 16 ms 18756 KB Output is correct
9 Correct 46 ms 19524 KB Output is correct
10 Correct 9 ms 13764 KB Output is correct
11 Correct 10 ms 13840 KB Output is correct
12 Correct 75 ms 15396 KB Output is correct
13 Correct 9 ms 13764 KB Output is correct
14 Correct 9 ms 13764 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 488 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 68 ms 1660 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 278 ms 11824 KB Output is correct
28 Runtime error 177 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 11724 KB Output is correct
2 Correct 70 ms 11708 KB Output is correct
3 Correct 81 ms 11820 KB Output is correct
4 Correct 88 ms 11768 KB Output is correct
5 Correct 81 ms 11708 KB Output is correct
6 Correct 12 ms 18792 KB Output is correct
7 Correct 12 ms 18756 KB Output is correct
8 Correct 12 ms 18756 KB Output is correct
9 Correct 44 ms 19536 KB Output is correct
10 Correct 9 ms 13764 KB Output is correct
11 Correct 8 ms 13764 KB Output is correct
12 Correct 72 ms 15344 KB Output is correct
13 Correct 9 ms 13764 KB Output is correct
14 Correct 9 ms 13764 KB Output is correct
15 Runtime error 245 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -