Submission #1201370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201370		shadow_sami	Wombats (IOI13_wombats)	C++20	Compilation error	0 ms	0 KiB

wombats

#include "artclass.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int R, C;
static int h[5000][200], v_cost[5000][200];

// A C×C matrix of ll
struct Mat {
    vector<vector<ll>> a;
    Mat(int C_=0, ll val = INF): a(C_, vector<ll>(C_, val)) {}
};

// per-row transfer matrices
vector<Mat> M;          // size R-1
// segment tree of size ~4R
vector<Mat> seg;

// compute M[i] in O(C^2)
void build_row(int i) {
    Mat &m = M[i];
    for(int a = 0; a < C; ++a) {
        static ll dist[200];
        // init
        for(int j = 0; j < C; ++j) dist[j] = INF;
        dist[a] = 0;
        // left→right
        for(int j = 1; j < C; ++j)
            dist[j] = min(dist[j], dist[j-1] + h[i][j-1]);
        // right→left
        for(int j = C-2; j >= 0; --j)
            dist[j] = min(dist[j], dist[j+1] + h[i][j]);
        // fill M[i][a][b]
        for(int b = 0; b < C; ++b)
            m.a[a][b] = dist[b] + v_cost[i][b];
    }
}

// min-plus multiply A⋆B, both C×C, in O(C^3)
Mat multiply(const Mat &A, const Mat &B) {
    Mat Rmat(C);
    for(int i = 0; i < C; ++i) {
        for(int k = 0; k < C; ++k) {
            ll v = A.a[i][k];
            if (v >= INF) continue;
            for(int j = 0; j < C; ++j) {
                Rmat.a[i][j] = min(Rmat.a[i][j], v + B.a[k][j]);
            }
        }
    }
    return Rmat;
}

// build segtree on [l..r)
void build_seg(int idx, int l, int r) {
    if (r - l == 1) {
        seg[idx] = M[l];
    } else {
        int mid = (l + r) >> 1;
        build_seg(idx*2, l, mid);
        build_seg(idx*2+1, mid, r);
        seg[idx] = multiply(seg[idx*2], seg[idx*2+1]);
    }
}

// point-update M[pos], then refresh tree
void update_seg(int idx, int l, int r, int pos) {
    if (r - l == 1) {
        seg[idx] = M[pos];
    } else {
        int mid = (l + r) >> 1;
        if (pos < mid) update_seg(idx*2, l, mid, pos);
        else           update_seg(idx*2+1, mid, r, pos);
        seg[idx] = multiply(seg[idx*2], seg[idx*2+1]);
    }
}

// query product on [ql..qr)
Mat query_seg(int idx, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return seg[idx];
    int mid = (l + r) >> 1;
    if (qr <= mid) return query_seg(idx*2, l, mid, ql, qr);
    if (ql >= mid) return query_seg(idx*2+1, mid, r, ql, qr);
    Mat left  = query_seg(idx*2, l, mid, ql, qr);
    Mat right = query_seg(idx*2+1, mid, r, ql, qr);
    return multiply(left, right);
}

// API

void init(int R_, int C_,
          int H_in[5000][200],
          int V_in[5000][200]) {
    R = R_; C = C_;
    // copy data
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            h[i][j]      = (j < C-1 ? H_in[i][j] : 0);
            v_cost[i][j] = (i < R-1 ? V_in[i][j] : 0);
        }
    }
    // allocate
    M.assign(R-1, Mat(C));
    seg.assign(4*(R-1), Mat(C));
    // build rows + segtree
    for (int i = 0; i < R-1; ++i)
        build_row(i);
    build_seg(1, 0, R-1);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    // rebuild row P
    build_row(P);
    update_seg(1, 0, R-1, P);
}

void changeV(int P, int Q, int W) {
    v_cost[P][Q] = W;
    // rebuild row P
    build_row(P);
    update_seg(1, 0, R-1, P);
}

int escape(int V1, int V2) {
    // query full product M[0]⋆⋯⋆M[R-2]
    Mat Mtot = query_seg(1, 0, R-1, 0, R-1);
    // entry [V1][V2]
    return (int)Mtot.a[V1][V2];
}

Compilation message (stderr)

wombats.cpp:1:10: fatal error: artclass.h: No such file or directory
    1 | #include "artclass.h"
      |          ^~~~~~~~~~~~
compilation terminated.