제출 #600267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600267		MilosMilutinovic	웜뱃 (IOI13_wombats)	C++14	76 / 100	7957 ms	262144 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 long long inf = 1e18;

int n, m, h[MAXR][MAXC], v[MAXR][MAXC], ls[MAXN], rs[MAXN], root, tsz;
long long 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];
      }
      long long 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];
        }
      }
    }
  }
}

long long up[MAXR], down[MAXR];

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++) {
      for (int k = 0; k < m; k++) {
        dp[c][i][j] = min(dp[c][i][j], dp[ls[c]][i][k] + dp[rs[c]][k][j] + v[mid][k]); // optimize this
      }
    }
  }
}

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];
}

컴파일 시 표준 에러 (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 pull(int, int, int)':
wombats.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void build(int&, int, int)':
wombats.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   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: 0 / 24