oj.uz

Submission #168244

# Submission time Handle Problem Language Result Execution time Memory
168244 2019-12-12T06:37:21 Z tri Wombats (IOI13_wombats) C++14
100 / 100
 8941 ms 148848 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 51320 KB Output is correct
2 Correct 66 ms 51320 KB Output is correct
3 Correct 135 ms 54052 KB Output is correct
4 Correct 68 ms 51284 KB Output is correct
5 Correct 65 ms 51192 KB Output is correct
6 Correct 53 ms 47324 KB Output is correct
7 Correct 54 ms 47352 KB Output is correct
8 Correct 54 ms 47352 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 47296 KB Output is correct
2 Correct 54 ms 47372 KB Output is correct
3 Correct 54 ms 47352 KB Output is correct
4 Correct 78 ms 59640 KB Output is correct
5 Correct 78 ms 59640 KB Output is correct
6 Correct 79 ms 59744 KB Output is correct
7 Correct 78 ms 59768 KB Output is correct
8 Correct 77 ms 59128 KB Output is correct
9 Correct 83 ms 59756 KB Output is correct
10 Correct 77 ms 59256 KB Output is correct
11 Correct 153 ms 62084 KB Output is correct
12 Correct 77 ms 59644 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 92012 KB Output is correct
2 Correct 781 ms 91524 KB Output is correct
3 Correct 815 ms 92020 KB Output is correct
4 Correct 821 ms 92024 KB Output is correct
5 Correct 799 ms 91636 KB Output is correct
6 Correct 54 ms 47352 KB Output is correct
7 Correct 54 ms 47352 KB Output is correct
8 Correct 54 ms 47352 KB Output is correct
9 Correct 1920 ms 92120 KB Output is correct
10 Correct 59 ms 53240 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 60292 KB Output is correct
2 Correct 73 ms 60276 KB Output is correct
3 Correct 76 ms 60284 KB Output is correct
4 Correct 111 ms 61688 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 92104 KB Output is correct
2 Correct 785 ms 91512 KB Output is correct
3 Correct 813 ms 92152 KB Output is correct
4 Correct 814 ms 91896 KB Output is correct
5 Correct 798 ms 91636 KB Output is correct
6 Correct 72 ms 60280 KB Output is correct
7 Correct 72 ms 60308 KB Output is correct
8 Correct 77 ms 60280 KB Output is correct
9 Correct 112 ms 61656 KB Output is correct
10 Correct 64 ms 51192 KB Output is correct
11 Correct 65 ms 51272 KB Output is correct
12 Correct 135 ms 54124 KB Output is correct
13 Correct 68 ms 51320 KB Output is correct
14 Correct 65 ms 51268 KB Output is correct
15 Correct 53 ms 47352 KB Output is correct
16 Correct 54 ms 47352 KB Output is correct
17 Correct 54 ms 47352 KB Output is correct
18 Correct 79 ms 59772 KB Output is correct
19 Correct 79 ms 59760 KB Output is correct
20 Correct 79 ms 59668 KB Output is correct
21 Correct 79 ms 59772 KB Output is correct
22 Correct 77 ms 59128 KB Output is correct
23 Correct 79 ms 59768 KB Output is correct
24 Correct 77 ms 59384 KB Output is correct
25 Correct 156 ms 62044 KB Output is correct
26 Correct 79 ms 59744 KB Output is correct
27 Correct 1922 ms 92144 KB Output is correct
28 Correct 2076 ms 104056 KB Output is correct
29 Correct 2116 ms 102136 KB Output is correct
30 Correct 2187 ms 102136 KB Output is correct
31 Correct 2162 ms 105584 KB Output is correct
32 Correct 59 ms 53112 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 92048 KB Output is correct
2 Correct 785 ms 91692 KB Output is correct
3 Correct 815 ms 92100 KB Output is correct
4 Correct 817 ms 92124 KB Output is correct
5 Correct 797 ms 91704 KB Output is correct
6 Correct 74 ms 60280 KB Output is correct
7 Correct 74 ms 60280 KB Output is correct
8 Correct 79 ms 60408 KB Output is correct
9 Correct 112 ms 61700 KB Output is correct
10 Correct 65 ms 51320 KB Output is correct
11 Correct 66 ms 51320 KB Output is correct
12 Correct 135 ms 54204 KB Output is correct
13 Correct 80 ms 51192 KB Output is correct
14 Correct 67 ms 51292 KB Output is correct
15 Correct 2145 ms 147576 KB Output is correct
16 Correct 8590 ms 148848 KB Output is correct
17 Correct 54 ms 47352 KB Output is correct
18 Correct 55 ms 47352 KB Output is correct
19 Correct 54 ms 47352 KB Output is correct
20 Correct 79 ms 59736 KB Output is correct
21 Correct 78 ms 59740 KB Output is correct
22 Correct 79 ms 59784 KB Output is correct
23 Correct 79 ms 59772 KB Output is correct
24 Correct 76 ms 59128 KB Output is correct
25 Correct 78 ms 59768 KB Output is correct
26 Correct 77 ms 59236 KB Output is correct
27 Correct 155 ms 62264 KB Output is correct
28 Correct 78 ms 59664 KB Output is correct
29 Correct 1928 ms 92112 KB Output is correct
30 Correct 2094 ms 103804 KB Output is correct
31 Correct 8354 ms 146064 KB Output is correct
32 Correct 8414 ms 146308 KB Output is correct
33 Correct 2121 ms 102264 KB Output is correct
34 Correct 8534 ms 144356 KB Output is correct
35 Correct 2182 ms 102176 KB Output is correct
36 Correct 8633 ms 144224 KB Output is correct
37 Correct 2169 ms 105632 KB Output is correct
38 Correct 8090 ms 146876 KB Output is correct
39 Correct 58 ms 53112 KB Output is correct
40 Correct 8941 ms 144508 KB Output is correct