oj.uz

Submission #395031

# Submission time Handle Problem Language Result Execution time Memory
395031 2021-04-27T16:10:49 Z phathnv Wombats (IOI13_wombats) C++11
100 / 100
 6022 ms 183324 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

const int BLOCK_SIZE = 10;

int n, m, h[5000][200], v[5000][200], d[1024][200][200], o[201];

void update(int pos, int id = 1, int l = 0, int r = 499){
    if (pos < l || r < pos)
        return;
    if (l == r){
        memset(d[id], 0x3f, sizeof(d[id]));
        for(int i = 0; i < n; i++)
            d[id][i][i] = 0;
        for(int k = pos * BLOCK_SIZE; k < (pos + 1) * BLOCK_SIZE; k++)
            for(int i = 0; i < n; i++){
                for(int j = n - 2; j >= 0; j--)
                    d[id][i][j] = min(d[id][i][j], d[id][i][j + 1] + h[k][j]);
                for(int j = 1; j < n; j++)
                    d[id][i][j] = min(d[id][i][j], d[id][i][j - 1] + h[k][j - 1]);
                for(int j = 0; j < n; j++)
                    d[id][i][j] += v[k][j];
            }
        return;
    }
    int mid = (l + r) >> 1;
    update(pos, id << 1, l, mid);
    update(pos, id << 1 | 1, mid + 1, r);
    memset(d[id], 0x3f, sizeof(d[id]));
    memset(o, 0, sizeof(o));
    o[n] = n - 1;
    for(int i = 0; i < n; i++)
        for(int j = n - 1; j >= 0; j--)
            for(int k = o[j]; k <= o[j + 1]; k++)
                if (d[id][i][j] >= d[id << 1][i][k] + d[id << 1 | 1][k][j]){
                    d[id][i][j] = d[id << 1][i][k] + d[id << 1 | 1][k][j];
                    o[j] = k;
                }
}

void init(int r, int c, int _h[5000][200], int _v[5000][200]){
    m = r;
    n = c;
    memset(h, 0x3f, sizeof(h));
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c - 1; j++)
            h[i][j] = _h[i][j];
    for(int i = 0; i < r - 1; i++)
        for(int j = 0; j < c; j++)
            v[i][j] = _v[i][j];
    for(int i = 0; i <= 499; i++)
        update(i);
}

void changeH(int p, int q, int w){
    h[p][q] = w;
    update(p / BLOCK_SIZE);
}

void changeV(int p, int q, int w){
    v[p][q] = w;
    update(p / BLOCK_SIZE);
}

int escape(int v1, int v2){
    return d[1][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 168 ms 168572 KB Output is correct
2 Correct 146 ms 168508 KB Output is correct
3 Correct 234 ms 171228 KB Output is correct
4 Correct 169 ms 168520 KB Output is correct
5 Correct 164 ms 168400 KB Output is correct
6 Correct 105 ms 160560 KB Output is correct
7 Correct 93 ms 160580 KB Output is correct
8 Correct 95 ms 160600 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 160580 KB Output is correct
2 Correct 102 ms 160636 KB Output is correct
3 Correct 102 ms 160644 KB Output is correct
4 Correct 146 ms 160716 KB Output is correct
5 Correct 144 ms 160692 KB Output is correct
6 Correct 150 ms 160720 KB Output is correct
7 Correct 161 ms 160724 KB Output is correct
8 Correct 140 ms 160684 KB Output is correct
9 Correct 155 ms 160740 KB Output is correct
10 Correct 142 ms 160688 KB Output is correct
11 Correct 269 ms 162992 KB Output is correct
12 Correct 140 ms 160732 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 160908 KB Output is correct
2 Correct 928 ms 160984 KB Output is correct
3 Correct 927 ms 160996 KB Output is correct
4 Correct 975 ms 160996 KB Output is correct
5 Correct 957 ms 160880 KB Output is correct
6 Correct 110 ms 160664 KB Output is correct
7 Correct 110 ms 160644 KB Output is correct
8 Correct 117 ms 160592 KB Output is correct
9 Correct 1483 ms 160992 KB Output is correct
10 Correct 114 ms 160640 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 172440 KB Output is correct
2 Correct 157 ms 172408 KB Output is correct
3 Correct 193 ms 172444 KB Output is correct
4 Correct 213 ms 173892 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 953 ms 160876 KB Output is correct
2 Correct 947 ms 160984 KB Output is correct
3 Correct 926 ms 160884 KB Output is correct
4 Correct 934 ms 160964 KB Output is correct
5 Correct 929 ms 160876 KB Output is correct
6 Correct 174 ms 172356 KB Output is correct
7 Correct 160 ms 172380 KB Output is correct
8 Correct 197 ms 172356 KB Output is correct
9 Correct 204 ms 173824 KB Output is correct
10 Correct 179 ms 168512 KB Output is correct
11 Correct 152 ms 168520 KB Output is correct
12 Correct 244 ms 171216 KB Output is correct
13 Correct 176 ms 168472 KB Output is correct
14 Correct 165 ms 168524 KB Output is correct
15 Correct 94 ms 160640 KB Output is correct
16 Correct 94 ms 160660 KB Output is correct
17 Correct 110 ms 160644 KB Output is correct
18 Correct 134 ms 160632 KB Output is correct
19 Correct 134 ms 160696 KB Output is correct
20 Correct 135 ms 160684 KB Output is correct
21 Correct 135 ms 160656 KB Output is correct
22 Correct 141 ms 160680 KB Output is correct
23 Correct 138 ms 160676 KB Output is correct
24 Correct 131 ms 160708 KB Output is correct
25 Correct 204 ms 163012 KB Output is correct
26 Correct 138 ms 160696 KB Output is correct
27 Correct 1447 ms 160992 KB Output is correct
28 Correct 1663 ms 174096 KB Output is correct
29 Correct 1671 ms 172204 KB Output is correct
30 Correct 1724 ms 172020 KB Output is correct
31 Correct 1669 ms 175244 KB Output is correct
32 Correct 114 ms 160580 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 160908 KB Output is correct
2 Correct 879 ms 160916 KB Output is correct
3 Correct 921 ms 161108 KB Output is correct
4 Correct 911 ms 161164 KB Output is correct
5 Correct 904 ms 160876 KB Output is correct
6 Correct 179 ms 172536 KB Output is correct
7 Correct 180 ms 172344 KB Output is correct
8 Correct 186 ms 172356 KB Output is correct
9 Correct 211 ms 173992 KB Output is correct
10 Correct 147 ms 168516 KB Output is correct
11 Correct 145 ms 168504 KB Output is correct
12 Correct 214 ms 171188 KB Output is correct
13 Correct 160 ms 168516 KB Output is correct
14 Correct 142 ms 168444 KB Output is correct
15 Correct 2927 ms 173764 KB Output is correct
16 Correct 5886 ms 183324 KB Output is correct
17 Correct 107 ms 160608 KB Output is correct
18 Correct 115 ms 160600 KB Output is correct
19 Correct 106 ms 160672 KB Output is correct
20 Correct 122 ms 160708 KB Output is correct
21 Correct 119 ms 160648 KB Output is correct
22 Correct 118 ms 160804 KB Output is correct
23 Correct 129 ms 160708 KB Output is correct
24 Correct 123 ms 160692 KB Output is correct
25 Correct 118 ms 160612 KB Output is correct
26 Correct 115 ms 160708 KB Output is correct
27 Correct 203 ms 163188 KB Output is correct
28 Correct 117 ms 160736 KB Output is correct
29 Correct 1417 ms 160960 KB Output is correct
30 Correct 1593 ms 176564 KB Output is correct
31 Correct 5436 ms 180736 KB Output is correct
32 Correct 5544 ms 180824 KB Output is correct
33 Correct 1655 ms 174172 KB Output is correct
34 Correct 5934 ms 178220 KB Output is correct
35 Correct 1683 ms 174144 KB Output is correct
36 Correct 5772 ms 178348 KB Output is correct
37 Correct 1640 ms 178256 KB Output is correct
38 Correct 5503 ms 181404 KB Output is correct
39 Correct 105 ms 160656 KB Output is correct
40 Correct 6022 ms 178176 KB Output is correct