Submission #605680

#	Time	Username	Problem	Language	Result	Execution time	Memory
605680		skittles1412	Wombats (IOI13_wombats)	C++17	55 / 100	20056 ms	42024 KiB

wombats

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

#ifdef __cplusplus
extern "C" {
#endif

void init(int R, int C, int H[5000][200], int V[5000][200]);
void changeH(int P, int Q, int W);
void changeV(int P, int Q, int W);
int escape(int V1, int V2);

#ifdef __cplusplus
}
#endif

const int maxn = 5005, maxm = 105;

template <int N, int M>
using mat = array<array<int, M>, N>;

template <int A, int B, int C>
mat<A, C> mul(const mat<A, B>& x, const mat<B, C>& y) {
    mat<A, C> ans;
    for (auto& a : ans) {
        a.fill(1e9);
    }
    for (int i = 0; i < A; i++) {
        for (int j = 0; j < B; j++) {
            for (int k = 0; k < C; k++) {
                ans[i][k] = min(ans[i][k], x[i][j] + y[j][k]);
            }
        }
    }
    return ans;
}

int n, m, t, last_upd, harr[5000][200], varr[5000][200];
mat<maxm, maxm> ans;

mat<maxm, maxm> solve(int l, int r) {
    mat<maxm, maxm> ans {};
    for (int i = 0; i < m; i++) {
        auto& dp = ans[i];
        dp.fill(1e9);
        dp[i] = 0;
        for (int j = l; j < r; j++) {
            array<int, maxm> ndp;
            ndp.fill(1e9);
            int psum[m + 1];
            psum[0] = 0;
            partial_sum(harr[j], harr[j] + m, psum + 1);
            int ans = 1e9;
            for (int k = 0; k < m; k++) {
                ans = min(ans, dp[k] - psum[k]);
                if (!i && j == n - 1) {
                    dbg(k, ans, varr[j][k], psum[k]);
                }
                ndp[k] = min(ndp[k], ans + varr[j][k] + psum[k]);
            }
            ans = 1e9;
            for (int k = m - 1; k >= 0; k--) {
                ans = min(ans, dp[k] + psum[k]);
                ndp[k] = min(ndp[k], ans + varr[j][k] - psum[k]);
            }
            swap(dp, ndp);
        }
    }
    return ans;
}

void init(int _n, int _m, int _harr[5000][200], int _varr[5000][200]) {
    n = _n;
    m = _m;
    memcpy(harr, _harr, sizeof(harr));
    memcpy(varr, _varr, sizeof(varr));
    last_upd = -1;
}

void changeH(int x, int y, int w) {
    t++;
    harr[x][y] = w;
}

void changeV(int x, int y, int w) {
    t++;
    varr[x][y] = w;
}

int escape(int a, int b) {
    if (last_upd < t) {
        ans = solve(0, n);
        last_upd = t;
    }
    return ans[a][b];
}

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;
      |      ^~~

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