제출 #356674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
356674		hamerin	웜뱃 (IOI13_wombats)	C++17	100 / 100	11630 ms	197764 KiB

wombats

#include "wombats.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const int L = 15;
const int pinf = numeric_limits<int>::max() / 2;
const int ninf = numeric_limits<int>::min() / 2;

int R, C;
vector<vector<int>> H, V;

namespace DPHelper {
    vector<vector<int>> base_get(int r) {
        vector<vector<int>> ret(C, vector<int>(C, pinf));
        for (int k = 0; k < C; k++) {
            for (int i = 0; i < C - k; i++) {
                if (k == 0)
                    ret[i][i] = 0;
                else
                    ret[i][i + k] = ret[i + k][i] = ret[i + 1][i + k] + H[r][i];
            }
        }

        if (r != R - 1) {
            for (int i = 0; i < C; i++)
                for (int j = 0; j < C; j++)
                    ret[i][j] += V[r][j];
        }

        return ret;
    }

    vector<vector<int>> mer(const vector<vector<int>>& lhs, const vector<vector<int>>& rhs) {
        vector<vector<int>> ret(C, vector<int>(C, pinf));
        vector<vector<int>> opt(C, vector<int>(C));

        for (int k = 0; k < C; k++) {
            for (int i = 0; i < C - k; i++) {
                if (k == 0) {
                    for (int j = 0; j < C; j++) {
                        if (ret[i][i] > lhs[i][j] + rhs[j][i]) {
                            ret[i][i] = lhs[i][j] + rhs[j][i];
                            opt[i][i] = j;
                        }
                    }
                } else {
                    for (int j = opt[i][i + k - 1]; j <= opt[i + 1][i + k]; j++) {
                        if (ret[i][i + k] > lhs[i][j] + rhs[j][i + k]) {
                            ret[i][i + k] = lhs[i][j] + rhs[j][i + k];
                            opt[i][i + k] = j;
                        }
                    }
                    for (int j = opt[i + k - 1][i]; j <= opt[i + k][i + 1]; j++) {
                        if (ret[i + k][i] > lhs[i + k][j] + rhs[j][i]) {
                            ret[i + k][i] = lhs[i + k][j] + rhs[j][i];
                            opt[i + k][i] = j;
                        }
                    }
                }
            }
        }

        return ret;
    }

    vector<vector<int>> base_solve(int s, int e) {
        auto ret = base_get(s);

        for (int r = s + 1; r <= e; r++)
            ret = mer(ret, base_get(r));

        return ret;
    }
};  // namespace DPHelper

class SegTree {
   public:
    int N{};
    vector<vector<vector<int>>> vl;

    SegTree() = default;

    SegTree(int N) {
        this->N = N;
        vl.resize(N << 2);
    }

    void init(int s, int e, int n) {
        if (e - s < L) {
            vl[n] = DPHelper::base_solve(s, e);
            return;
        }

        int m = (s + e) >> 1, k = n << 1;
        init(s, m, k);
        init(m + 1, e, k | 1);

        vl[n] = DPHelper::mer(vl[k], vl[k | 1]);
    }

    inline void init() {
        init(0, N - 1, 1);
    }

    void update(int s, int e, int n, int p) {
        if (e < p || p < s) return;
        if (e - s < L) {
            vl[n] = DPHelper::base_solve(s, e);
            return;
        }

        int m = (s + e) >> 1, k = n << 1;
        update(s, m, k, p);
        update(m + 1, e, k | 1, p);

        vl[n] = DPHelper::mer(vl[k], vl[k | 1]);
    }

    inline void update(int p) {
        update(0, N - 1, 1, p);
    }

    int query(int V1, int V2) {
        return vl[1][V1][V2];
    }
};

SegTree ST;

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    R = r, C = c;
    H.resize(R);
    V.resize(R - 1);

    for (int i = 0; i < R; i++) copy(h[i], h[i] + C - 1, back_inserter(H[i]));
    for (int i = 0; i < R - 1; i++) copy(v[i], v[i] + C, back_inserter(V[i]));

    ST = SegTree(R);
    ST.init();
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    ST.update(P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    ST.update(P);
}

int escape(int V1, int V2) {
    return ST.query(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