Problem "Wombats" From IOI 2013 Day 1

wombats.cpp

#include "wombats.h"

#include <algorithm>
#include <cstring>

using namespace std;

#define K 15
#define INF 5000010

int R, C;
int H[5000][200];
int V[5000][200];

int T[1024][200][200];

static void hsmooth(int* A, int r) {
  for(int i = 1; i < C; i++) {
    A[i] = min(A[i], A[i - 1] + H[r][i - 1]);
  }
  for(int i = C - 2; i >= 0; i--) {
    A[i] = min(A[i], A[i + 1] + H[r][i]);
  }
}

static void compute_base(int A[200][200], int rlo, int rhi) {
  for(int i = 0; i < C; i++) {
    int* B = A[i];
    for(int j = 0; j < C; j++) {
      B[j] = i == j ? 0 : INF;
    }

    for(int r = rlo; r < rhi; r++) {
      hsmooth(B, r);
      for(int j = 0; j < C; j++) {
        B[j] += V[r][j];
      }
    }
  }
}

static void solve(int i, int jlo, int jhi, int klo, int khi,
                  int R[200], int X[200], int Y[200][200]) {
  if(jlo == jhi) {
    return;
  }

  int jmd = (jlo + jhi) / 2;
  int kmd = klo;

  R[jmd] = X[kmd] + Y[kmd][jmd];
  for(int k = klo + 1; k < khi; k++) {
    int v = X[k] + Y[k][jmd];
    if(v < R[jmd]) {
      R[jmd] = v;
      kmd = k;
    }
  }

  solve(i, jlo, jmd, klo, kmd + 1, R, X, Y);
  solve(i, jmd + 1, jhi, kmd, khi, R, X, Y);
}

static void compute_merge(int R[200][200], int X[200][200], int Y[200][200]) {
  for(int i = 0; i < C; i++) {
    solve(i, 0, C, 0, C, R[i], X[i], Y);
  }
}

static void update(int x, int rlo, int rhi, int rupdate) {
  if(rlo + 1 >= R) {
  } else if(rhi - rlo == K) {
    compute_base(T[x], rlo, min(R - 1, rhi));
  } else {
    int rmd = (rlo + rhi) / 2;
    if(rupdate == -1 || rupdate < rmd) {
      update(2 * x + 1, rlo, rmd, rupdate);
    }
    if(rupdate == -1 || rmd <= rupdate) {
      update(2 * x + 2, rmd, rhi, rupdate);
    }
    if(rmd + 1 < R) {
      compute_merge(T[x], T[2 * x + 1], T[2 * x + 2]);
    } else {
      memcpy(T[x], T[2 * x + 1], sizeof(T[x]));
    }
  }
}

void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) {
  R = RR;
  C = CC;
  memcpy(H, HH, sizeof(H));
  memcpy(V, VV, sizeof(V));
  update(0, 0, 512 * K, -1);
}

void changeH(int P, int Q, int W) {
  H[P][Q] = W;
  update(0, 0, 512 * K, P);
}

void changeV(int P, int Q, int W) {
  V[P][Q] = W;
  update(0, 0, 512 * K, P);
}

int escape(int V1, int V2) {
  hsmooth(T[0][V1], R - 1);
  return T[0][V1][V2];
}