Submission #168244

#	Time	Username	Problem	Language	Result	Execution time	Memory
168244		tri	Wombats (IOI13_wombats)	C++14	100 / 100	8941 ms	148848 KiB

wombats

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

int R, C;

int h[6000][200], v[6000][200];

const int BSZ = 20;
const int NUMBLK = 256;

int blks[NUMBLK][200][200];
int tr[512][200][200];

int cDist[200]; // temporary workspace

// sR inclusive, eR exclusive
void buildBlock(int sR, int eR, int block[200][200]) {
    // dist[i][j] has destination i

    for (int stC = 0; stC < C; stC++) {
        for (int i = 0; i < C; i++) {
            cDist[i] = 1e6;
        }
        cDist[stC] = 0;

//        ps("stC:", stC);

        for (int cR = sR; cR < eR; cR++) {
            for (int i = 1; i < C; i++) {
                cDist[i] = min(cDist[i], cDist[i - 1] + h[cR][i - 1]);
            }

            for (int i = C - 2; i >= 0; i--) {
                cDist[i] = min(cDist[i], cDist[i + 1] + h[cR][i]);
            }

            for (int i = 0; i < C; i++) {
                cDist[i] += v[cR][i];
            }

//            ps(cR);
//            for (int i = 0; i < C; i++) {
//                pr(cDist[i], " ");
//            }
//            ps();
        }
        for (int i = 0; i < C; i++) {
            block[stC][i] = cDist[i];
        }
    }
//    ps("built");
//    if (sR == 0) {
//        DEBUG = false;
//    }
}

int start;

void merge(int a[200][200], int b[200][200], int ans[200][200], int eL, int eR, int xL, int xR) {
    int midE = (eL + eR) / 2;

    int minC = 1e9;
    int minX = -1;
    for (int x = xL; x <= xR; x++) {
        int cCost = a[start][x] + b[x][midE];
        if (cCost < minC) {
            minC = cCost;
            minX = x;
        }
    }

    ans[start][midE] = minC;

    if (eL < midE) {
        merge(a, b, ans, eL, midE - 1, xL, minX);
    }
    if (midE < eR) {
        merge(a, b, ans, midE + 1, eR, minX, xR);
    }
}

void merge(int a[200][200], int b[200][200], int ans[200][200]) {
    for (start = 0; start < C; start++) {
        merge(a, b, ans, 0, C - 1, 0, C - 1);
    }
}

void build(int i, int l, int r) {
    if (l == r) {
        memcpy(tr[i], blks[l], sizeof(blks[l]));
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    merge(tr[i * 2], tr[i * 2 + 1], tr[i]);
}

void recalculate(int i, int l, int r, int x) {
    if (l == r) {
        memcpy(tr[i], blks[l], sizeof(blks[l]));
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        recalculate(i * 2, l, mid, x);
    } else {
        recalculate(i * 2 + 1, mid + 1, r, x);
    }
    merge(tr[i * 2], tr[i * 2 + 1], tr[i]);
}

void update(int bI) {
    int bS = bI * BSZ, bE = (bI + 1) * BSZ; // bE is exclusive
    buildBlock(bS, bE, blks[bI]);
    recalculate(1, 0, NUMBLK - 1, bI);
}

void init(int iR, int iC, int iH[5000][200], int iV[5000][200]) {
    R = iR, C = iC;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C - 1; j++) {
            h[i][j] = iH[i][j];
        }
    }
    for (int i = 0; i < R - 1; i++) {
        for (int j = 0; j < C; j++) {
            v[i][j] = iV[i][j];
        }
    }

    for (int i = R; i < 6000; i++) {
        for (int j = 0; j < C - 1; j++) {
            h[i][j] = 1e6;
        }
    }

    for (int i = R - 1; i < 6000 - 1; i++) {
        for (int j = 0; j < C; j++) {
            v[i][j] = 0;
        }
    }

//    ps(R, C);
//    for(int i = 0; i < C-1; i++){
//        pr(h[0][i], " ");
//    }
//    ps();
//    ps("fin");

    for (int bI = 0; bI < NUMBLK; bI++) {
        int bS = bI * BSZ, bE = (bI + 1) * BSZ; // bE is exclusive
        buildBlock(bS, bE, blks[bI]);
    }

    build(1, 0, NUMBLK - 1);

//    for (int i = 0; i < C; i++) {
//        for (int j = 0; j < C; j++) {
//            pr(tr[1][i][j], " ");
//        }
//        ps();
//    }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    update(P / BSZ);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    update(P / BSZ);
}


int escape(int C1, int C2) {
    int ans = tr[1][C1][C2];
    return ans;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  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