oj.uz

Submission #439114

# Submission time Handle Problem Language Result Execution time Memory
439114 2021-06-29T08:53:14 Z prvocislo Wombats (IOI13_wombats) C++17
100 / 100
 4389 ms 195356 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

const int R = 5120, C = 205, B = 10, V = 512, inf = 1e9 + 5;
//const int R = 4, C = 4, B = 1, V = 4, inf = 1e9 + 5;
int h[R][C], v[R][C], st[V*2][C][C], l[V*2], r[V*2], o[C+1];
void print(string s, int m[C][C])
{
    cout << s << "\n";
    for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) cout << m[i][j] << " \n"[j==C-1];
    cout << "\n";
}
void upd(int &a, const int &b) { a = min(a, b); }
void update(int li, int ri, int vr = 0)
{
    if (ri < l[vr] || li > r[vr]) return; // tento update sa ma netyka
    if (l[vr] == r[vr]) // dosli sme na list
    {
        for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) st[vr][i][j] = inf;
        for (int c1 = 0; c1 < C; c1++)
        {
            st[vr][c1][c1] = 0;
            for (int i = l[vr] * B; i < (r[vr] + 1) * B; i++)
            {
                for (int c2 = 0; c2 < C - 1; c2++) upd(st[vr][c1][c2 + 1], st[vr][c1][c2] + h[i][c2]);
                for (int c2 = C - 1; c2 > 0; c2--) upd(st[vr][c1][c2 - 1], st[vr][c1][c2] + h[i][c2 - 1]);
                for (int c2 = 0; c2 < C; c2++) st[vr][c1][c2] += v[i][c2];
            }
        }
        //print("leaf " + to_string(vr) + ":", st[vr]);
        return;
    }
    update(li, ri, vr * 2 + 1), update(li, ri, vr * 2 + 2);
    fill(o, o + C, 0); o[C] = C - 1;
    for (int c1 = 0; c1 < C; c1++) for (int c2 = C - 1; c2 >= 0; c2--)
    {
        pair<int, int> best(inf, -o[c2]); // kde sme nasli minimalnu hodnotu a jej index
        for (int k = o[c2]; k <= o[c2 + 1]; k++) 
            best = min(best, {st[vr*2+1][c1][k]+st[vr*2+2][k][c2], -k});
        st[vr][c1][c2] = best.first;
        o[c2] = -best.second;
    }
    //print("non-leaf " + to_string(vr) + ":", st[vr]);
}
void init(int ri, int ci, int h[5000][200], int v[5000][200]) {
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) ::h[i][j] = inf;
    for (int i = V - 1; i < V * 2; i++) l[i] = r[i] = i - (V - 1);
    for (int i = V - 2; i >= 0; i--) l[i] = l[i*2+1], r[i] = r[i*2+2];
    for (int i = 0; i < ri; i++) for (int j = 0; j < ci - 1; j++) ::h[i][j] = h[i][j];
    for (int i = 0; i < ri - 1; i++) for (int j = 0; j < ci; j++) ::v[i][j] = v[i][j];
    update(0, V - 1);
}
void changeH(int i, int j, int val) {
    h[i][j] = val;
    update(i/B, i/B);
}
void changeV(int i, int j, int val) {
    v[i][j] = val;
    update(i/B, i/B);
}
int escape(int v1, int v2) {
    return st[0][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 4022 ms 180676 KB Output is correct
2 Correct 3842 ms 180628 KB Output is correct
3 Correct 3995 ms 183396 KB Output is correct
4 Correct 3974 ms 180624 KB Output is correct
5 Correct 3852 ms 180628 KB Output is correct
6 Correct 1112 ms 172688 KB Output is correct
7 Correct 1068 ms 172656 KB Output is correct
8 Correct 1129 ms 172572 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 172632 KB Output is correct
2 Correct 1143 ms 172684 KB Output is correct
3 Correct 1072 ms 172632 KB Output is correct
4 Correct 1154 ms 172688 KB Output is correct
5 Correct 1122 ms 172740 KB Output is correct
6 Correct 1081 ms 172676 KB Output is correct
7 Correct 1072 ms 172784 KB Output is correct
8 Correct 1101 ms 172708 KB Output is correct
9 Correct 1076 ms 172636 KB Output is correct
10 Correct 1087 ms 172752 KB Output is correct
11 Correct 1193 ms 175176 KB Output is correct
12 Correct 1139 ms 172728 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1628 ms 172984 KB Output is correct
2 Correct 1604 ms 173016 KB Output is correct
3 Correct 1671 ms 172900 KB Output is correct
4 Correct 1666 ms 173032 KB Output is correct
5 Correct 1611 ms 173152 KB Output is correct
6 Correct 1087 ms 172620 KB Output is correct
7 Correct 1083 ms 172720 KB Output is correct
8 Correct 1094 ms 172600 KB Output is correct
9 Correct 3834 ms 173000 KB Output is correct
10 Correct 1156 ms 172684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3846 ms 184580 KB Output is correct
2 Correct 3722 ms 184688 KB Output is correct
3 Correct 4048 ms 184576 KB Output is correct
4 Correct 4194 ms 185944 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 172936 KB Output is correct
2 Correct 1655 ms 172912 KB Output is correct
3 Correct 1725 ms 173088 KB Output is correct
4 Correct 1714 ms 173000 KB Output is correct
5 Correct 1591 ms 172984 KB Output is correct
6 Correct 3803 ms 184596 KB Output is correct
7 Correct 3689 ms 184660 KB Output is correct
8 Correct 3818 ms 184580 KB Output is correct
9 Correct 3973 ms 185952 KB Output is correct
10 Correct 3897 ms 180552 KB Output is correct
11 Correct 4070 ms 180628 KB Output is correct
12 Correct 4389 ms 183340 KB Output is correct
13 Correct 3860 ms 180612 KB Output is correct
14 Correct 3761 ms 180544 KB Output is correct
15 Correct 1080 ms 172588 KB Output is correct
16 Correct 1075 ms 172616 KB Output is correct
17 Correct 1077 ms 172656 KB Output is correct
18 Correct 1076 ms 172740 KB Output is correct
19 Correct 1082 ms 172688 KB Output is correct
20 Correct 1093 ms 172620 KB Output is correct
21 Correct 1069 ms 172724 KB Output is correct
22 Correct 1090 ms 172772 KB Output is correct
23 Correct 1092 ms 172772 KB Output is correct
24 Correct 1083 ms 172852 KB Output is correct
25 Correct 1156 ms 175184 KB Output is correct
26 Correct 1107 ms 172640 KB Output is correct
27 Correct 3652 ms 173048 KB Output is correct
28 Correct 3848 ms 188728 KB Output is correct
29 Correct 3903 ms 186252 KB Output is correct
30 Correct 3933 ms 186136 KB Output is correct
31 Correct 3923 ms 190520 KB Output is correct
32 Correct 1118 ms 172716 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 173192 KB Output is correct
2 Correct 1613 ms 173104 KB Output is correct
3 Correct 1596 ms 173060 KB Output is correct
4 Correct 1563 ms 172956 KB Output is correct
5 Correct 1594 ms 173084 KB Output is correct
6 Correct 3698 ms 184580 KB Output is correct
7 Correct 3753 ms 184664 KB Output is correct
8 Correct 3743 ms 184672 KB Output is correct
9 Correct 3720 ms 186176 KB Output is correct
10 Correct 3595 ms 180736 KB Output is correct
11 Correct 3660 ms 180756 KB Output is correct
12 Correct 3678 ms 183504 KB Output is correct
13 Correct 3796 ms 180700 KB Output is correct
14 Correct 3968 ms 180744 KB Output is correct
15 Correct 1273 ms 194248 KB Output is correct
16 Correct 4041 ms 195356 KB Output is correct
17 Correct 1071 ms 172636 KB Output is correct
18 Correct 1078 ms 172752 KB Output is correct
19 Correct 1067 ms 172740 KB Output is correct
20 Correct 1084 ms 172740 KB Output is correct
21 Correct 1074 ms 172820 KB Output is correct
22 Correct 1074 ms 172660 KB Output is correct
23 Correct 1133 ms 172796 KB Output is correct
24 Correct 1091 ms 172720 KB Output is correct
25 Correct 1085 ms 172652 KB Output is correct
26 Correct 1077 ms 172888 KB Output is correct
27 Correct 1165 ms 175248 KB Output is correct
28 Correct 1082 ms 172836 KB Output is correct
29 Correct 4069 ms 173156 KB Output is correct
30 Correct 3638 ms 188528 KB Output is correct
31 Correct 3694 ms 192892 KB Output is correct
32 Correct 3834 ms 192888 KB Output is correct
33 Correct 3821 ms 186228 KB Output is correct
34 Correct 4019 ms 190164 KB Output is correct
35 Correct 3964 ms 186208 KB Output is correct
36 Correct 4024 ms 190144 KB Output is correct
37 Correct 3949 ms 190524 KB Output is correct
38 Correct 4001 ms 193716 KB Output is correct
39 Correct 1091 ms 172612 KB Output is correct
40 Correct 4170 ms 190400 KB Output is correct