oj.uz

Submission #795623

# Submission time Handle Problem Language Result Execution time Memory
795623 2023-07-27T11:48:56 Z erray Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 46500 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 = 100;
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 1703 ms 24496 KB Output is correct
2 Correct 1580 ms 24520 KB Output is correct
3 Correct 1711 ms 27288 KB Output is correct
4 Correct 1666 ms 24456 KB Output is correct
5 Correct 1745 ms 24508 KB Output is correct
6 Correct 1 ms 2516 KB Output is correct
7 Correct 1 ms 2516 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 2388 KB Output is correct
3 Correct 1 ms 2388 KB Output is correct
4 Correct 3 ms 2492 KB Output is correct
5 Correct 3 ms 2516 KB Output is correct
6 Correct 2 ms 2496 KB Output is correct
7 Correct 2 ms 2516 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 2 ms 2516 KB Output is correct
10 Correct 2 ms 2516 KB Output is correct
11 Correct 59 ms 4824 KB Output is correct
12 Correct 2 ms 2492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 2812 KB Output is correct
2 Correct 1195 ms 2760 KB Output is correct
3 Correct 1480 ms 2728 KB Output is correct
4 Correct 1492 ms 2816 KB Output is correct
5 Correct 1435 ms 2772 KB Output is correct
6 Correct 1 ms 2388 KB Output is correct
7 Correct 1 ms 2388 KB Output is correct
8 Correct 1 ms 2388 KB Output is correct
9 Correct 6068 ms 2772 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 1623 ms 28632 KB Output is correct
2 Correct 1689 ms 28620 KB Output is correct
3 Correct 1708 ms 28620 KB Output is correct
4 Correct 1663 ms 29924 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 2812 KB Output is correct
2 Correct 1174 ms 3004 KB Output is correct
3 Correct 1467 ms 2772 KB Output is correct
4 Correct 1451 ms 2808 KB Output is correct
5 Correct 1412 ms 2772 KB Output is correct
6 Correct 1719 ms 28620 KB Output is correct
7 Correct 1680 ms 28732 KB Output is correct
8 Correct 1680 ms 28616 KB Output is correct
9 Correct 1697 ms 29908 KB Output is correct
10 Correct 1699 ms 24496 KB Output is correct
11 Correct 1626 ms 24516 KB Output is correct
12 Correct 1851 ms 27280 KB Output is correct
13 Correct 1699 ms 24520 KB Output is correct
14 Correct 1634 ms 24516 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 2492 KB Output is correct
19 Correct 2 ms 2516 KB Output is correct
20 Correct 2 ms 2516 KB Output is correct
21 Correct 2 ms 2516 KB Output is correct
22 Correct 2 ms 2516 KB Output is correct
23 Correct 2 ms 2516 KB Output is correct
24 Correct 2 ms 2516 KB Output is correct
25 Correct 58 ms 4852 KB Output is correct
26 Correct 3 ms 2516 KB Output is correct
27 Correct 6312 ms 2836 KB Output is correct
28 Correct 7013 ms 36400 KB Output is correct
29 Correct 8057 ms 31128 KB Output is correct
30 Correct 8273 ms 31072 KB Output is correct
31 Correct 7214 ms 38184 KB Output is correct
32 Correct 2 ms 2516 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1448 ms 2828 KB Output is correct
2 Correct 1213 ms 2804 KB Output is correct
3 Correct 1450 ms 2756 KB Output is correct
4 Correct 1453 ms 2772 KB Output is correct
5 Correct 1421 ms 2772 KB Output is correct
6 Correct 1610 ms 28620 KB Output is correct
7 Correct 1590 ms 28604 KB Output is correct
8 Correct 1568 ms 28628 KB Output is correct
9 Correct 1617 ms 29880 KB Output is correct
10 Correct 1710 ms 24512 KB Output is correct
11 Correct 1750 ms 24516 KB Output is correct
12 Correct 1687 ms 27288 KB Output is correct
13 Correct 1648 ms 24520 KB Output is correct
14 Correct 1632 ms 24404 KB Output is correct
15 Correct 2443 ms 45988 KB Output is correct
16 Execution timed out 20056 ms 46500 KB Time limit exceeded
17 Halted 0 ms 0 KB -