Submission #474808

#	Time	Username	Problem	Language	Result	Execution time	Memory
474808		emuyumi	Wombats (IOI13_wombats)	C++17	76 / 100	20053 ms	37768 KiB

wombats

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

using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MR = 5000, MC = 200, BSZ = 70;

int R, C, H[MR][MC], V[MR][MC];
int N, blk[MR], blkL[MR], blkR[MR];
struct Item{
    int d[MC][MC];
    Item(){ ms(d, 0); }
    int& operator()(int a, int b){ return d[a][b]; }
    void setid(){ ms(d, 0x3f); for (int i = 0; i < C; ++i) d[i][i] = 0; }
    void set(int r){
        Item rhs;
        for (int i = 0; i < C; ++i){
            d[i][i] = V[r][i];
            rhs(i, i) = 0;
            for (int j = i - 1; j >= 0; --j){
                d[i][j] = d[i][j + 1] - V[r][j + 1] + H[r][j] + V[r][j];
                rhs(i, j) = rhs(i, j + 1) + H[r + 1][j];
            }
            for (int j = i + 1; j < C; ++j){
                d[i][j] = d[i][j - 1] - V[r][j - 1] + H[r][j - 1] + V[r][j];
                rhs(i, j) = rhs(i, j - 1) + H[r + 1][j - 1];
            }
        }
        merge(rhs);
    }
    void merge(Item &rhs){
        Item lhs = *this;
        memcpy(lhs.d, d, MC * MC * sizeof(int));
// lhs.print();
// rhs.print();
        ms(d, 0);
        for (int i = 0; i < C; ++i){
            for (int k = 0; k < C; ++k){
                if (lhs(i, k) + rhs(k, i) < lhs(i, d[i][i]) + rhs(d[i][i], i)) d[i][i] = k;
            }
        }
        for (int sz = 2; sz <= C; ++sz){
            for (int l = 0, r = sz - 1; r < C; ++l, ++r){
                for (int k = d[l][r - 1]; k <= d[l + 1][r]; ++k){
                    if (lhs(l, k) + rhs(k, r) < lhs(l, d[l][r]) + rhs(d[l][r], r)) d[l][r] = k;
                }
            }
            for (int l = sz - 1, r = 0; l < C; ++l, ++r){
                for (int k = d[l - 1][r]; k <= d[l][r + 1]; ++k){
                    if (lhs(l, k) + rhs(k, r) < lhs(l, d[l][r]) + rhs(d[l][r], r)) d[l][r] = k;
                }
            }
        }
// print();
// cout << '\n' << '\n' << '\n';
        for (int i = 0; i < C; ++i){
            for (int j = 0; j < C; ++j){
                d[i][j] = lhs(i, d[i][j]) + rhs(d[i][j], j);
            }
        }

// for (int j = C - 1; j >= 0; --j){
//     d[i][j] = inf;
//     for (int k = 0; k < C; ++k){
//         d[i][j] = min(d[i][j], lhs(i, k) + rhs(k, j));
//     }
// }

    }
    void print(){
        cout << "~~~~~~~~~" << '\n';
        for (int i = 0; i < C; ++i){
            for (int j = 0; j < C; ++j){
                cout << d[i][j] << " ";
            }
            cout << '\n';
        }
        cout << "~~~~~~~~~" << '\n';
    }
} arr[MR / BSZ + 1], cur, ans;

void fix_block(int b){
// cout << "fixing : " << b << '\n';
    arr[b].set(blkL[b]);
    for (int i = blkL[b] + 1; i <= blkR[b]; ++i){
        cur.set(i);
        arr[b].merge(cur);
    }
}

void fix_all(){
    memcpy(ans.d, arr[0].d, MC * MC * sizeof(int));
    for (int i = 1; i < N; ++i){
        ans.merge(arr[i]);
    }
}

void init(int r, int c, int h[5000][200], int v[5000][200]){
    R = r, C = c;
    memcpy(H, h, MR * MC * sizeof(int));
    memcpy(V, v, MR * MC * sizeof(int));

    ms(blkL, 0x3f); 
    for (int i = 0; i < R - 1; ++i){
        int b = i / BSZ;
        blk[i] = b;
        blkL[b] = min(blkL[b], i);
        blkR[b] = max(blkR[b], i);
    }
    N = (R - 2) / BSZ + 1;

    for (int i = 0; i < N; ++i) fix_block(i);
    fix_all();
}

void changeH(int p, int q, int w){
    H[p][q] = w;
    fix_block(blk[p]);
    if (p != 0 && blk[p] != blk[p - 1]){
        fix_block(blk[p - 1]);
    }
    fix_all();
}

void changeV(int p, int q, int w){
    V[p][q] = w;
    fix_block(blk[p]);
    fix_all();
}

int escape(int v1, int v2){
    return ans(v1, v2);
}

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: 21 / 21
• Subtask 6: 0 / 24