제출 #414996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414996		KoD	Wombats (IOI13_wombats)	C++17	100 / 100	10261 ms	155592 KiB

wombats

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

template <class T> using Vec = std::vector<T>;

namespace solver {
    constexpr int LOG = 13;
    constexpr int INF = 1000000000;

    struct Data {
        Vec<Vec<int>> dist;
        int right;
        Data(): dist(), right() {}
    };

    int R, C;
    Vec<Vec<int>> hori, vert;

    Vec<Data> seg;

    void set_size(const int s) {
        int t = 1;
        while (t < s) t <<= 1;
        seg.resize(2 * t);
    }

    Vec<Vec<int>> calc_row(const int i) {
        Vec<Vec<int>> ret(C, Vec<int>(C));
        Vec<int> sum(C);
        for (int j = 0; j < C - 1; ++j) {
            sum[j + 1] = sum[j] + hori[i][j];
        }
        for (int j = 0; j < C; ++j) {
            for (int k = j + 1; k < C; ++k) {
                ret[j][k] = ret[k][j] = sum[k] - sum[j];
            }
        }
        return ret;
    }

    bool setmin(int &x, const int y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }

    void absorb(Vec<Vec<int>>& cur, const int i, const Vec<Vec<int>>& add) {
        Vec<Vec<int>> idx(C, Vec<int>(C));
        Vec<Vec<int>> next(C, Vec<int>(C, INF));
        for (int j = 0; j < C; ++j) {
            for (int k = 0; k < C; ++k) {
                if (setmin(next[j][j], cur[j][k] + vert[i][k] + add[k][j])) {
                    idx[j][j] = k;
                }
            }
        }
        for (int width = 1; width < C; ++width) {
            for (int j = 0; j + width < C; ++j) {
                for (int k = idx[j][j + width - 1]; k <= idx[j + 1][j + width]; ++k) {
                    if (setmin(next[j][j + width], cur[j][k] + vert[i][k] + add[k][j + width])) {
                        idx[j][j + width] = k;
                    }
                }
            }
            for (int j = width; j < C; ++j) {
                for (int k = idx[j - 1][j - width]; k <= idx[j][j - width + 1]; ++k) {
                    if (setmin(next[j][j - width], cur[j][k] + vert[i][k] + add[k][j - width])) {
                        idx[j][j - width] = k;
                    }
                }
            }
        }
        cur = std::move(next);
    }

    void recalc(const int sec) {
        const int left = LOG * sec;
        const int right = std::min(left + LOG, R);
        auto& data = seg[sec + seg.size() / 2];
        data.dist = calc_row(left);
        data.right = left;
        for (int i = left + 1; i < right; ++i) {
            absorb(data.dist, data.right, calc_row(i));
            data.right += 1;
        }
    }

    void fetch(const int k) {
        seg[k] = seg[2 * k];
        if (!seg[2 * k + 1].dist.empty()) {
            absorb(seg[k].dist, seg[k].right, seg[2 * k + 1].dist);
            seg[k].right = seg[2 * k + 1].right;
        }
    }

    void update(int k) {
        k += (int) seg.size() / 2;
        while (k > 1) {
            k >>= 1;
            fetch(k);
        }
    }
};
 
void init(int N, int M, int H[5000][200], int V[5000][200]) {
    using namespace solver;
    R = N;
    C = M;
    hori = Vec<Vec<int>>(R, Vec<int>(C - 1));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C - 1; ++j) {
            hori[i][j] = H[i][j];
        }
    }
    vert = Vec<Vec<int>>(R - 1, Vec<int>(C));
    for (int i = 0; i < R - 1; ++i) {
        for (int j = 0; j < C; ++j) {
            vert[i][j] = V[i][j];
        }
    }
    const int size = (R + LOG - 1) / LOG;
    set_size(size);
    for (int i = 0; i < size; ++i) {
        recalc(i);
    }
    for (int i = (int) seg.size() / 2 - 1; i > 0; --i) {
        fetch(i);
    }
}

void changeH(int P, int Q, int W) {
    using namespace solver;
    hori[P][Q] = W;
    recalc(P / LOG);
    update(P / LOG);
}

void changeV(int P, int Q, int W) {
    using namespace solver;
    vert[P][Q] = W;
    recalc(P / LOG);
    update(P / LOG);
}

int escape(int V1, int V2) {
    using namespace solver;
    return seg[1].dist[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;
      |      ^~~

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