oj.uz

Submission #795637

# Submission time Handle Problem Language Result Execution time Memory
795637 2023-07-27T11:57:04 Z erray Wombats (IOI13_wombats) C++17
100 / 100
 6476 ms 248432 KB 
#undef DEBUG 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "debug.h"
#else 
  #define debug(...) void(37)
#endif

const int mxC = 200;  
using node = array<array<int, mxC>, mxC>;
const int inf = int(1e9);
node emp;
int R, C;

node unite(node& l, node& r) {
  node res = emp;
  array<array<int, mxC>, mxC> opt{};
  for (int i = 0; i < C; ++i) {
    for (int j = C - 1; j >= 0; --j) {
      for (int k = (i == 0 ? 0 : opt[i - 1][j]); k <= (j == C - 1 ? C - 1 : opt[i][j + 1]); ++k) {
        int add = l[i][k] + r[k][j];
        if (add < res[i][j]) {
          res[i][j] = add;
          opt[i][j] = k;
        }
      }
    }
  }
  debug(opt);
  return res;
}

struct SegTree {
  vector<node> tree;
  int n;
  #define def int mid = (l + r) >> 1, rv = (v + (mid - l) * 2)
  void modify(int v, int l, int r, int p, node x) {
    debug(v, l, r);
    if (l + 1 == r) {
      tree[v] = x;
      return;  
    }
    def;
    if (p < mid) {
      modify(v + 1, l, mid, p, x);
    } else {
      modify(rv, mid, r, p, x);
    }
    tree[v] = unite(tree[v + 1], tree[rv]);
  }
  void modify(int p, node x) {
    modify(0, 0, n, p, x);
  }
  SegTree(int _n) : n(_n) {
    tree.resize(n * 2 - 1);    
  }
  SegTree() { }
};


SegTree st;
int BLOCK = 7;
vector<vector<int>> H;
vector<vector<int>> V;
void Upd(int x) {
  node res;
  bool first = true;
  for (int i = x * BLOCK; i < min(R, (x + 1) * BLOCK); ++i) {
    //debug(i);
    {
      node add = emp;
      for (int j = 0; j < C; ++j) {
        add[j][j] = 0;
      }
      for (int j = 0; j < C; ++j) {
        for (int k = j + 1; k < C; ++k) {
          add[j][k] = add[k][j] = add[j][k - 1] + H[i][k - 1];
        }       
      } 
      debug(add);
      res = (first ? add : unite(res, add));
      first = false;
    }
    debug(res);
    if (i < R - 1) {
      node add = emp;
      for (int j = 0; j < C; ++j) {
        add[j][j] = V[i][j];
      }
      debug(add);
      res = unite(res, add);
    }
    debug(i, res);
  }
  st.modify(x, res);
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
  for (int i = 0; i < mxC; ++i) {
    for (int j = 0; j < mxC; ++j) {
      emp[i][j] = inf;
    }
  }
  swap(R, _R);
  swap(C, _C);
  H.resize(R, vector<int>(C - 1));
  V.resize(R - 1, vector<int>(C));
  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C - 1; ++j) {
      H[i][j] = _H[i][j];
    }
  }
  for (int i = 0; i < R - 1; ++i) {
    for (int j = 0; j < C; ++j) {
      V[i][j] = _V[i][j];
    }
  }
  debug(H, V);
  st = SegTree((R + BLOCK - 1) / BLOCK);
  debug(st.n);
  for (int i = 0; i * BLOCK < R; ++i) {
    Upd(i);
  }
  debug("init end");
}

void changeH(int P, int Q, int W) {
  H[P][Q] = W;
  Upd(P / BLOCK);
}

void changeV(int P, int Q, int W) {
  V[P][Q] = W;
  Upd(P / BLOCK);
}                    

int escape(int V1, int V2) { 
  debug(st.tree[0]);
  return st.tree[0][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 591 ms 234136 KB Output is correct
2 Correct 559 ms 234140 KB Output is correct
3 Correct 616 ms 236172 KB Output is correct
4 Correct 584 ms 234036 KB Output is correct
5 Correct 549 ms 234140 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 1 ms 2488 KB Output is correct
8 Correct 1 ms 2388 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2484 KB Output is correct
3 Correct 1 ms 2388 KB Output is correct
4 Correct 2 ms 3128 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 57 ms 4596 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 8448 KB Output is correct
2 Correct 127 ms 8428 KB Output is correct
3 Correct 152 ms 8404 KB Output is correct
4 Correct 154 ms 8364 KB Output is correct
5 Correct 144 ms 8404 KB Output is correct
6 Correct 1 ms 2484 KB Output is correct
7 Correct 2 ms 2388 KB Output is correct
8 Correct 1 ms 2388 KB Output is correct
9 Correct 554 ms 8460 KB Output is correct
10 Correct 2 ms 2516 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 238248 KB Output is correct
2 Correct 572 ms 238156 KB Output is correct
3 Correct 585 ms 238244 KB Output is correct
4 Correct 626 ms 239164 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 8448 KB Output is correct
2 Correct 122 ms 8456 KB Output is correct
3 Correct 155 ms 8404 KB Output is correct
4 Correct 147 ms 8476 KB Output is correct
5 Correct 146 ms 8404 KB Output is correct
6 Correct 564 ms 238376 KB Output is correct
7 Correct 573 ms 238156 KB Output is correct
8 Correct 605 ms 238256 KB Output is correct
9 Correct 598 ms 239196 KB Output is correct
10 Correct 567 ms 234120 KB Output is correct
11 Correct 573 ms 234140 KB Output is correct
12 Correct 614 ms 236012 KB Output is correct
13 Correct 574 ms 234144 KB Output is correct
14 Correct 561 ms 234084 KB Output is correct
15 Correct 2 ms 2388 KB Output is correct
16 Correct 1 ms 2388 KB Output is correct
17 Correct 1 ms 2388 KB Output is correct
18 Correct 2 ms 3156 KB Output is correct
19 Correct 3 ms 3156 KB Output is correct
20 Correct 3 ms 3156 KB Output is correct
21 Correct 2 ms 3128 KB Output is correct
22 Correct 2 ms 3136 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 3 ms 3156 KB Output is correct
25 Correct 56 ms 4568 KB Output is correct
26 Correct 2 ms 3128 KB Output is correct
27 Correct 543 ms 8460 KB Output is correct
28 Correct 1907 ms 242792 KB Output is correct
29 Correct 1952 ms 199992 KB Output is correct
30 Correct 1941 ms 200140 KB Output is correct
31 Correct 1963 ms 243768 KB Output is correct
32 Correct 2 ms 2516 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 8380 KB Output is correct
2 Correct 142 ms 8404 KB Output is correct
3 Correct 154 ms 8404 KB Output is correct
4 Correct 150 ms 8452 KB Output is correct
5 Correct 157 ms 8404 KB Output is correct
6 Correct 556 ms 238244 KB Output is correct
7 Correct 565 ms 238228 KB Output is correct
8 Correct 578 ms 238252 KB Output is correct
9 Correct 587 ms 239216 KB Output is correct
10 Correct 575 ms 234108 KB Output is correct
11 Correct 557 ms 234144 KB Output is correct
12 Correct 617 ms 236032 KB Output is correct
13 Correct 580 ms 234060 KB Output is correct
14 Correct 572 ms 234140 KB Output is correct
15 Correct 3560 ms 246384 KB Output is correct
16 Correct 6476 ms 248432 KB Output is correct
17 Correct 2 ms 2388 KB Output is correct
18 Correct 1 ms 2388 KB Output is correct
19 Correct 1 ms 2388 KB Output is correct
20 Correct 3 ms 3156 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 3 ms 3156 KB Output is correct
23 Correct 3 ms 3156 KB Output is correct
24 Correct 3 ms 3156 KB Output is correct
25 Correct 3 ms 3156 KB Output is correct
26 Correct 3 ms 3136 KB Output is correct
27 Correct 63 ms 4928 KB Output is correct
28 Correct 3 ms 3156 KB Output is correct
29 Correct 551 ms 8360 KB Output is correct
30 Correct 1967 ms 242852 KB Output is correct
31 Correct 5815 ms 247128 KB Output is correct
32 Correct 5632 ms 247232 KB Output is correct
33 Correct 1908 ms 200092 KB Output is correct
34 Correct 5682 ms 203928 KB Output is correct
35 Correct 1934 ms 200256 KB Output is correct
36 Correct 5720 ms 204560 KB Output is correct
37 Correct 2100 ms 244488 KB Output is correct
38 Correct 5759 ms 248408 KB Output is correct
39 Correct 2 ms 2516 KB Output is correct
40 Correct 5815 ms 204428 KB Output is correct