oj.uz

Submission #516424

# Submission time Handle Problem Language Result Execution time Memory
516424 2022-01-21T09:57:41 Z 600Mihnea Wombats (IOI13_wombats) C++17
55 / 100
 3182 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 j = 0; j < m; j++) {
      for (int k = 0; k < m; k++) {
        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;
        }
      }
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      assert(opt[i][j] != -1);
      if (j + 1 < m) assert(opt[i][j] <= opt[i][j + 1]);
      if (i - 1 >= 0) assert(opt[i][j] >= opt[i - 1][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 8 ms 13764 KB Output is correct
2 Correct 8 ms 13864 KB Output is correct
3 Correct 76 ms 15448 KB Output is correct
4 Correct 9 ms 13868 KB Output is correct
5 Correct 8 ms 13764 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 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 65 ms 1504 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 788 ms 11820 KB Output is correct
2 Correct 671 ms 11708 KB Output is correct
3 Correct 811 ms 11828 KB Output is correct
4 Correct 794 ms 11872 KB Output is correct
5 Correct 763 ms 11708 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 3094 ms 11820 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 12 ms 18756 KB Output is correct
2 Correct 13 ms 18708 KB Output is correct
3 Correct 14 ms 18744 KB Output is correct
4 Correct 44 ms 19584 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 11820 KB Output is correct
2 Correct 686 ms 11704 KB Output is correct
3 Correct 795 ms 11824 KB Output is correct
4 Correct 793 ms 11872 KB Output is correct
5 Correct 789 ms 11716 KB Output is correct
6 Correct 13 ms 18800 KB Output is correct
7 Correct 16 ms 18756 KB Output is correct
8 Correct 12 ms 18800 KB Output is correct
9 Correct 45 ms 19476 KB Output is correct
10 Correct 8 ms 13764 KB Output is correct
11 Correct 8 ms 13816 KB Output is correct
12 Correct 73 ms 15444 KB Output is correct
13 Correct 9 ms 13764 KB Output is correct
14 Correct 9 ms 13880 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 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 460 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 64 ms 1468 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 3182 ms 11832 KB Output is correct
28 Runtime error 178 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 828 ms 11720 KB Output is correct
2 Correct 756 ms 11704 KB Output is correct
3 Correct 822 ms 11824 KB Output is correct
4 Correct 810 ms 11824 KB Output is correct
5 Correct 866 ms 11712 KB Output is correct
6 Correct 12 ms 18756 KB Output is correct
7 Correct 12 ms 18756 KB Output is correct
8 Correct 15 ms 18768 KB Output is correct
9 Correct 53 ms 19576 KB Output is correct
10 Correct 9 ms 13768 KB Output is correct
11 Correct 9 ms 13764 KB Output is correct
12 Correct 77 ms 15352 KB Output is correct
13 Correct 14 ms 13764 KB Output is correct
14 Correct 17 ms 13868 KB Output is correct
15 Runtime error 296 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -