Submission #795489

#	Time	Username	Problem	Language	Result	Execution time	Memory
795489		erray	Wombats (IOI13_wombats)	C++17	0 / 100	20041 ms	11324 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

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

#ifdef LOCAL
  const int mxC = 4;
#else 
  const int mxC = 200;
#endif
  
using node = array<array<int, mxC>, mxC>;
const int inf = int(1e9);
node emp;
node unite(node l, node r) {
  node res = emp;
  array<array<int, mxC>, mxC> opt{};
  for (int i = 0; i < mxC; ++i) {
    for (int j = mxC - 1; j >= 0; --j) {
      for (int k = (i == 0 ? 0 : opt[i - 1][j]); k <= (j == mxC - 1 ? mxC - 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 << 1);    
  }
  SegTree() { }
};


SegTree st;
int BLOCK = 5000;
int R, C;
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;
      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) {
  return st.tree[0][V1][V2];
}

Compilation message (stderr)

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24