oj.uz

Submission #474808

# Submission time Handle Problem Language Result Execution time Memory
474808 2021-09-19T23:54:40 Z emuyumi Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 37768 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1707 ms 23992 KB Output is correct
2 Correct 1688 ms 24004 KB Output is correct
3 Correct 1792 ms 26820 KB Output is correct
4 Correct 1729 ms 23884 KB Output is correct
5 Correct 1710 ms 23996 KB Output is correct
6 Correct 10 ms 20044 KB Output is correct
7 Correct 10 ms 19964 KB Output is correct
8 Correct 10 ms 20044 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19960 KB Output is correct
2 Correct 12 ms 19964 KB Output is correct
3 Correct 11 ms 20044 KB Output is correct
4 Correct 11 ms 20044 KB Output is correct
5 Correct 11 ms 20096 KB Output is correct
6 Correct 12 ms 20172 KB Output is correct
7 Correct 12 ms 20044 KB Output is correct
8 Correct 12 ms 20016 KB Output is correct
9 Correct 11 ms 20044 KB Output is correct
10 Correct 12 ms 20104 KB Output is correct
11 Correct 87 ms 22428 KB Output is correct
12 Correct 11 ms 20088 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 20300 KB Output is correct
2 Correct 1661 ms 20280 KB Output is correct
3 Correct 2121 ms 20300 KB Output is correct
4 Correct 1937 ms 20300 KB Output is correct
5 Correct 2386 ms 20300 KB Output is correct
6 Correct 10 ms 20044 KB Output is correct
7 Correct 10 ms 20044 KB Output is correct
8 Correct 10 ms 20044 KB Output is correct
9 Correct 9391 ms 20284 KB Output is correct
10 Correct 10 ms 20044 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1705 ms 27944 KB Output is correct
2 Correct 1709 ms 27932 KB Output is correct
3 Correct 1747 ms 28068 KB Output is correct
4 Correct 1761 ms 29304 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 20300 KB Output is correct
2 Correct 1681 ms 20272 KB Output is correct
3 Correct 2141 ms 20292 KB Output is correct
4 Correct 1943 ms 20284 KB Output is correct
5 Correct 2358 ms 20300 KB Output is correct
6 Correct 1686 ms 28020 KB Output is correct
7 Correct 1685 ms 27928 KB Output is correct
8 Correct 1728 ms 27852 KB Output is correct
9 Correct 1788 ms 29412 KB Output is correct
10 Correct 1716 ms 24008 KB Output is correct
11 Correct 1671 ms 24128 KB Output is correct
12 Correct 1768 ms 26768 KB Output is correct
13 Correct 1746 ms 24012 KB Output is correct
14 Correct 1717 ms 24012 KB Output is correct
15 Correct 11 ms 20044 KB Output is correct
16 Correct 10 ms 20060 KB Output is correct
17 Correct 10 ms 20044 KB Output is correct
18 Correct 11 ms 20096 KB Output is correct
19 Correct 11 ms 20092 KB Output is correct
20 Correct 12 ms 20104 KB Output is correct
21 Correct 11 ms 20044 KB Output is correct
22 Correct 11 ms 20028 KB Output is correct
23 Correct 12 ms 20092 KB Output is correct
24 Correct 11 ms 20044 KB Output is correct
25 Correct 89 ms 22452 KB Output is correct
26 Correct 11 ms 20044 KB Output is correct
27 Correct 9336 ms 20288 KB Output is correct
28 Correct 14455 ms 32028 KB Output is correct
29 Correct 17390 ms 30296 KB Output is correct
30 Correct 17162 ms 30300 KB Output is correct
31 Correct 14833 ms 33620 KB Output is correct
32 Correct 10 ms 20044 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1043 ms 20288 KB Output is correct
2 Correct 1665 ms 20296 KB Output is correct
3 Correct 2143 ms 20300 KB Output is correct
4 Correct 1961 ms 20300 KB Output is correct
5 Correct 2391 ms 20300 KB Output is correct
6 Correct 1704 ms 27976 KB Output is correct
7 Correct 1725 ms 27932 KB Output is correct
8 Correct 1720 ms 27948 KB Output is correct
9 Correct 1782 ms 29300 KB Output is correct
10 Correct 1748 ms 24080 KB Output is correct
11 Correct 1731 ms 23996 KB Output is correct
12 Correct 1792 ms 26764 KB Output is correct
13 Correct 1697 ms 24012 KB Output is correct
14 Correct 1689 ms 24012 KB Output is correct
15 Correct 5866 ms 37768 KB Output is correct
16 Execution timed out 20053 ms 36340 KB Time limit exceeded
17 Halted 0 ms 0 KB -