제출 #834736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834736		erdemkiraz	웜뱃 (IOI13_wombats)	C++11	100 / 100	6614 ms	195320 KiB

wombats

#include "wombats.h"
#include "iostream"
#include "algorithm"
#include "vector"
#include "set"
#include "map"
#include "cstring"
#include "string"
#include "vector"
#include "cassert"
#include "queue"
#include "cstdio"
#include "cstdlib"
#include "ctime"
#include "cmath"
#include "bitset"
#include "numeric"
#include "iomanip"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 5000 + 5;
const int M = 200 + 5;

int n, m;
int a[N][M], b[N][M];
int t[1024][M][M];

void row(int i, int dp[N]) {
    for(int j = m - 1; j >= 1; j--)
        dp[j] = min(dp[j], dp[j + 1] + a[i][j]);
    for(int j = 2; j <= m; j++)
        dp[j] = min(dp[j], dp[j - 1] + a[i][j - 1]);
}

void calcDp(int x, int l, int r) {
    for(int st = 1; st <= m; st++) {
        for(int i = 1; i <= m; i++)
            t[x][st][i] = 1e9 * (st != i);
        row(l, t[x][st]);
        for(int i = l; i < r; i++) {
            for(int nd = 1; nd <= m; nd++)
                t[x][st][nd] += b[i][nd];
            row(i + 1, t[x][st]);
        }
    }
}

int opt[M][M];

void solve(int x, int x1, int x2, int i, int l, int r, int optL, int optR, int b[M]) {
    if(l > r)
        return;
    int m = (l + r) >> 1;
    int opt = -1;
    t[x][i][m] = 1e9;
    for(int j = optL; j <= optR; j++) {
        int cost = t[x1][i][j] + b[j] + t[x2][j][m];
        if(cost < t[x][i][m]) {
            t[x][i][m] = cost;
            opt = j;
        }
    }
    solve(x, x1, x2, i, l, m - 1, optL, opt, b);
    solve(x, x1, x2, i, m + 1, r, opt, optR, b);
}

void calc(int x, int x1, int x2, int b[M]) {
    for(int i = 1; i <= m; i++)
        solve(x, x1, x2, i, 1, m, 1, m, b);
}

void init(int x, int l, int r) {
    if(r - l < 15) {
        calcDp(x, l, r);
        return;
    }
    int m = (l + r) >> 1;
    init(x + x, l, m);
    init(x + x + 1, m + 1, r);
    calc(x, x + x, x + x + 1, b[m]);
}

void update(int x, int l, int r, int v) {
    if(r - l < 15) {
        calcDp(x, l, r);
        return;
    }
    int m = (l + r) >> 1;
    if(v <= m)
        update(x + x, l, m, v);
    else
        update(x + x + 1, m + 1, r, v);
    calc(x, x + x, x + x + 1, b[m]);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R;
    m = C;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            a[i][j] = H[i - 1][j - 1], b[i][j] = V[i - 1][j - 1];
    init(1, 1, n);
}

void changeH(int x, int y, int v) {
    ++x;
    ++y;
    a[x][y] = v;
    update(1, 1, n, x);
}

void changeV(int x, int y, int v) {
    ++x;
    ++y;
    b[x][y] = v;
    update(1, 1, n, x);
}

int escape(int x, int y) {
    ++x;
    ++y;
    return t[1][x][y];
}

컴파일 시 표준 에러 (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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24