oj.uz

Submission #516409

# Submission time Handle Problem Language Result Execution time Memory
516409 2022-01-21T09:37:38 Z 600Mihnea Wombats (IOI13_wombats) C++17
28 / 100
 3379 ms 45192 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 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;
  int cost[M][M];
  Node() :
    l(0),
    r(0) {
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) cost[i][j] = 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];


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;
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < m; k++) {
        solution.cost[i][k] = min(solution.cost[i][k], A[i][j] + B[j][k]);
      }
    }
  }
}



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({});
  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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1444 KB Output is correct
2 Correct 1 ms 1412 KB Output is correct
3 Correct 1 ms 1444 KB Output is correct
4 Correct 9 ms 12288 KB Output is correct
5 Correct 8 ms 12288 KB Output is correct
6 Correct 8 ms 12288 KB Output is correct
7 Correct 9 ms 12204 KB Output is correct
8 Correct 12 ms 12288 KB Output is correct
9 Correct 11 ms 12268 KB Output is correct
10 Correct 12 ms 12216 KB Output is correct
11 Correct 94 ms 12372 KB Output is correct
12 Correct 9 ms 12288 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 45184 KB Output is correct
2 Correct 768 ms 45084 KB Output is correct
3 Correct 777 ms 45188 KB Output is correct
4 Correct 802 ms 45096 KB Output is correct
5 Correct 791 ms 45108 KB Output is correct
6 Correct 1 ms 1412 KB Output is correct
7 Correct 1 ms 1444 KB Output is correct
8 Correct 2 ms 1444 KB Output is correct
9 Correct 3379 ms 45192 KB Output is correct
10 Correct 2 ms 2260 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 17984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 45072 KB Output is correct
2 Correct 748 ms 45140 KB Output is correct
3 Correct 766 ms 45096 KB Output is correct
4 Correct 802 ms 45080 KB Output is correct
5 Correct 750 ms 45116 KB Output is correct
6 Runtime error 12 ms 17948 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 45096 KB Output is correct
2 Correct 758 ms 45084 KB Output is correct
3 Correct 773 ms 45172 KB Output is correct
4 Correct 796 ms 45076 KB Output is correct
5 Correct 758 ms 45088 KB Output is correct
6 Runtime error 11 ms 17936 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -