Submission #600282

#	Time	Username	Problem	Language	Result	Execution time	Memory
600282		MilosMilutinovic	Wombats (IOI13_wombats)	C++14	100 / 100	3941 ms	193572 KiB

wombats

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

using namespace std;

const int MAXR = 5005;
const int MAXC = 205;
const int MAXN = 3005;

const int inf = 1e9;

int n, m, h[MAXR][MAXC], v[MAXR][MAXC], ls[MAXN], rs[MAXN], root, tsz;
int dp[MAXN][MAXC][MAXC], pref[MAXC];

void buildSmall(int c, int l, int r) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      dp[c][i][j] = (i == j ? 0LL : inf);
    }
  }
  for (int i = l; i <= r; i++) {
    for (int x = 0; x < m; x++) {
      pref[0] = 0;
      for (int j = 1; j < m; j++) {
        pref[j] = pref[j - 1] + h[i][j - 1];
      }
      int mn = 1e18;
      for (int j = 0; j < m; j++) {
        mn = min(mn, dp[c][x][j] - pref[j]);
        dp[c][x][j] = min(dp[c][x][j], mn + pref[j]);
      }
      mn = 1e18;
      for (int j = m - 1; j >= 0; j--) {
        mn = min(mn, dp[c][x][j] + pref[j]);
        dp[c][x][j] = min(dp[c][x][j], mn - pref[j]);
      }
      if (i < r) {
        for (int j = 0; j < m; j++) {
          dp[c][x][j] += v[i][j];
        }
      }
    }
  }
}

int up[MAXR], down[MAXR];
int opt[MAXC][MAXC];

void pull(int c, int l, int r) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      dp[c][i][j] = inf;
    }
  }
  int mid = l + r >> 1;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      if (dp[ls[c]][i][j] + v[mid][j] + dp[rs[c]][j][i] < dp[c][i][i]) {
        dp[c][i][i] = dp[ls[c]][i][j] + v[mid][j] + dp[rs[c]][j][i];
        opt[i][i] = j;
      }
    }
  }
  for (int d = 1; d < m; d++) {
    for (int i = 0; i < m; i++) {
      if (i + d < m) {
        int j = i + d;
        for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
          if (dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j] < dp[c][i][j]) {
            dp[c][i][j] = dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j];
            opt[i][j] = k;
          }
        }
      }
      if (i >= d) {
        int j = i - d;
        for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
          if (dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j] < dp[c][i][j]) {
            dp[c][i][j] = dp[ls[c]][i][k] + v[mid][k] + dp[rs[c]][k][j];
            opt[i][j] = k;
          }
        }
      }
    }
  }
}

void build(int& c, int l, int r) {
  if (!c) c = ++tsz;
  if (r - l <= 10) {
    buildSmall(c, l, r);
    return;
  }
  int mid = l + r >> 1;
  build(ls[c], l, mid);
  build(rs[c], mid + 1, r);
  pull(c, l, r);
}

void update(int c, int l, int r, int i) {
  if (r - l <= 10) {
    buildSmall(c, l, r);
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    update(ls[c], l, mid, i);
  } else {
    update(rs[c], mid + 1, r, i);
  }
  pull(c, l, r);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  n = R;
  m = C;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m - 1; j++) {
      h[i][j] = H[i][j];
    }
  }
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < m; j++) {
      v[i][j] = V[i][j];
    }
  }
  build(root, 0, n - 1);
}

void changeH(int P, int Q, int W) {
  h[P][Q] = W;
  update(root, 0, n - 1, P);
}

void changeV(int P, int Q, int W) {
  v[P][Q] = W;
  update(root, 0, n - 1, P);
}

int escape(int V1, int V2) {
  return dp[root][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;
      |      ^~~
wombats.cpp: In function 'void buildSmall(int, int, int)':
wombats.cpp:27:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |       int mn = 1e18;
      |                ^~~~
wombats.cpp:32:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   32 |       mn = 1e18;
      |            ^~~~
wombats.cpp: In function 'void pull(int, int, int)':
wombats.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void build(int&, int, int)':
wombats.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:105:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24