oj.uz

Submission #795635

# Submission time Handle Problem Language Result Execution time Memory
795635 2023-07-27T11:52:41 Z erray Wombats (IOI13_wombats) C++17
100 / 100
 6581 ms 187324 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 = 10;
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 514 ms 166732 KB Output is correct
2 Correct 547 ms 166660 KB Output is correct
3 Correct 584 ms 168556 KB Output is correct
4 Correct 543 ms 166636 KB Output is correct
5 Correct 539 ms 166664 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 1 ms 2388 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 2 ms 2492 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 1 ms 2388 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2744 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2748 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 59 ms 5084 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 6888 KB Output is correct
2 Correct 151 ms 6868 KB Output is correct
3 Correct 199 ms 6868 KB Output is correct
4 Correct 189 ms 6868 KB Output is correct
5 Correct 183 ms 6820 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 1 ms 2388 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 733 ms 6880 KB Output is correct
10 Correct 1 ms 2516 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 170768 KB Output is correct
2 Correct 558 ms 170752 KB Output is correct
3 Correct 541 ms 170764 KB Output is correct
4 Correct 573 ms 172136 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6884 KB Output is correct
2 Correct 155 ms 6864 KB Output is correct
3 Correct 188 ms 6920 KB Output is correct
4 Correct 188 ms 6876 KB Output is correct
5 Correct 181 ms 6868 KB Output is correct
6 Correct 536 ms 170840 KB Output is correct
7 Correct 543 ms 170880 KB Output is correct
8 Correct 558 ms 170776 KB Output is correct
9 Correct 569 ms 172148 KB Output is correct
10 Correct 546 ms 166656 KB Output is correct
11 Correct 506 ms 166604 KB Output is correct
12 Correct 620 ms 169272 KB Output is correct
13 Correct 559 ms 166604 KB Output is correct
14 Correct 520 ms 166548 KB Output is correct
15 Correct 1 ms 2388 KB Output is correct
16 Correct 1 ms 2388 KB Output is correct
17 Correct 2 ms 2388 KB Output is correct
18 Correct 2 ms 2772 KB Output is correct
19 Correct 2 ms 2772 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 2 ms 2748 KB Output is correct
22 Correct 3 ms 2772 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 56 ms 4984 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 711 ms 6896 KB Output is correct
28 Correct 1965 ms 176028 KB Output is correct
29 Correct 1984 ms 145620 KB Output is correct
30 Correct 2009 ms 145592 KB Output is correct
31 Correct 1980 ms 177052 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 186 ms 6876 KB Output is correct
2 Correct 158 ms 6892 KB Output is correct
3 Correct 195 ms 6868 KB Output is correct
4 Correct 187 ms 6904 KB Output is correct
5 Correct 197 ms 6868 KB Output is correct
6 Correct 534 ms 170780 KB Output is correct
7 Correct 523 ms 170764 KB Output is correct
8 Correct 538 ms 170720 KB Output is correct
9 Correct 606 ms 172044 KB Output is correct
10 Correct 541 ms 166572 KB Output is correct
11 Correct 506 ms 166660 KB Output is correct
12 Correct 572 ms 169448 KB Output is correct
13 Correct 537 ms 166652 KB Output is correct
14 Correct 542 ms 166668 KB Output is correct
15 Correct 3176 ms 179524 KB Output is correct
16 Correct 6581 ms 181360 KB Output is correct
17 Correct 1 ms 2388 KB Output is correct
18 Correct 1 ms 2388 KB Output is correct
19 Correct 1 ms 2484 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 2 ms 2772 KB Output is correct
22 Correct 2 ms 2772 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 2 ms 2772 KB Output is correct
26 Correct 2 ms 2748 KB Output is correct
27 Correct 55 ms 5180 KB Output is correct
28 Correct 2 ms 2772 KB Output is correct
29 Correct 716 ms 6908 KB Output is correct
30 Correct 1900 ms 178596 KB Output is correct
31 Correct 5789 ms 186748 KB Output is correct
32 Correct 5921 ms 186700 KB Output is correct
33 Correct 1985 ms 147984 KB Output is correct
34 Correct 6058 ms 155104 KB Output is correct
35 Correct 1964 ms 147820 KB Output is correct
36 Correct 5972 ms 155116 KB Output is correct
37 Correct 2009 ms 180276 KB Output is correct
38 Correct 5894 ms 187324 KB Output is correct
39 Correct 2 ms 2516 KB Output is correct
40 Correct 6440 ms 155192 KB Output is correct