oj.uz

Submission #609152

# Submission time Handle Problem Language Result Execution time Memory
609152 2022-07-27T12:30:15 Z MohamedFaresNebili Wombats (IOI13_wombats) C++14
100 / 100
 4715 ms 183296 KB 
#include <bits/stdc++.h>
#include "wombats.h"
 
            using namespace std;
 
            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;
            using pi = pair<int, pair<int, int>>;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            const int oo = 1000 * 1000 * 1000 + 7;
 
            int R = 5000, C = 200, N = 500, batch = 10;
            int H[5000][200], V[5000][200], ST[1024][200][200], O[201];
 
            void update(int v, int lf, int rf, int lo, int hi) {
                if(lf > hi || rf < lo) return;
                if(lf == rf) {
                    for(int l = 0; l < C; l++)
                        for(int i = 0; i < C; i++)
                            ST[v][l][i] = oo;
                    for(int l = 0; l < C; l++) {
                        ST[v][l][l] = 0;
                        for(int i = lf * batch; i < (lf + 1) * batch; i++) {
                            for(int j = 1; j < C; j++)
                                ST[v][l][j] = min(ST[v][l][j], ST[v][l][j - 1] + H[i][j - 1]);
                            for(int j = C - 1; j > 0; j--)
                                ST[v][l][j - 1] = min(ST[v][l][j - 1], ST[v][l][j] + H[i][j - 1]);
                            for(int j = 0; j < C; j++)
                                ST[v][l][j] += V[i][j];
                        }
                    }
                    return;
                }
 
                int md = (lf + rf) / 2;
                update(v * 2, lf, md, lo, hi);
                update(v * 2 + 1, md + 1, rf, lo, hi);
 
                for(int l = 0; l < C; l++) O[l] = 0;
 
                for(int l = 0; l < C; l++) {
                    for(int i = C - 1; i >= 0; i--) {
                        pair<int, int> best = {oo, 0};
                        for(int j = O[i]; j <= O[i + 1]; j++)
                            best = min(best, {ST[v * 2][l][j] + ST[v * 2 + 1][j][i], -j});
                        ST[v][l][i] = best.first;
                        O[i] = -best.second;
                    }
                }
            }
            void init(int r, int c, int h[5000][200], int v[5000][200]) {
                for(int l = 0; l < R; l++)
                    for(int i = 0; i < C; i++)
                        H[l][i] = oo;
                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];
                O[C] = C - 1;
                update(1, 0, N - 1, 0, N - 1);
            }
 
            void changeH(int P, int Q, int W) {
                H[P][Q] = W;
                update(1, 0, N - 1, P / batch, P / batch);
            }
            void changeV(int P, int Q, int W) {
                V[P][Q] = W;
                update(1, 0, N - 1, P / batch, P / batch);
            }
 
            int escape(int V1, int V2) {
                return ST[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 3881 ms 168556 KB Output is correct
2 Correct 3965 ms 168492 KB Output is correct
3 Correct 3943 ms 170032 KB Output is correct
4 Correct 3986 ms 168492 KB Output is correct
5 Correct 3645 ms 168492 KB Output is correct
6 Correct 1328 ms 160752 KB Output is correct
7 Correct 1390 ms 160672 KB Output is correct
8 Correct 1311 ms 160716 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1291 ms 160672 KB Output is correct
2 Correct 1279 ms 160680 KB Output is correct
3 Correct 1348 ms 160728 KB Output is correct
4 Correct 1325 ms 160692 KB Output is correct
5 Correct 1294 ms 160668 KB Output is correct
6 Correct 1303 ms 160724 KB Output is correct
7 Correct 1302 ms 160628 KB Output is correct
8 Correct 1306 ms 160648 KB Output is correct
9 Correct 1293 ms 160756 KB Output is correct
10 Correct 1308 ms 160676 KB Output is correct
11 Correct 1365 ms 161772 KB Output is correct
12 Correct 1297 ms 160612 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 161040 KB Output is correct
2 Correct 1755 ms 160976 KB Output is correct
3 Correct 1775 ms 160936 KB Output is correct
4 Correct 1937 ms 160892 KB Output is correct
5 Correct 1810 ms 161036 KB Output is correct
6 Correct 1326 ms 160884 KB Output is correct
7 Correct 1354 ms 160636 KB Output is correct
8 Correct 1351 ms 160740 KB Output is correct
9 Correct 3812 ms 160932 KB Output is correct
10 Correct 1436 ms 160684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3956 ms 172408 KB Output is correct
2 Correct 3668 ms 172404 KB Output is correct
3 Correct 3610 ms 172608 KB Output is correct
4 Correct 3720 ms 173816 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1776 ms 161032 KB Output is correct
2 Correct 1826 ms 160988 KB Output is correct
3 Correct 1878 ms 161080 KB Output is correct
4 Correct 1818 ms 161000 KB Output is correct
5 Correct 1879 ms 161000 KB Output is correct
6 Correct 3588 ms 172548 KB Output is correct
7 Correct 3558 ms 172528 KB Output is correct
8 Correct 3635 ms 172480 KB Output is correct
9 Correct 3851 ms 173840 KB Output is correct
10 Correct 3887 ms 168516 KB Output is correct
11 Correct 3773 ms 168528 KB Output is correct
12 Correct 3962 ms 171092 KB Output is correct
13 Correct 3992 ms 168596 KB Output is correct
14 Correct 3581 ms 168524 KB Output is correct
15 Correct 1300 ms 160620 KB Output is correct
16 Correct 1315 ms 160744 KB Output is correct
17 Correct 1306 ms 160608 KB Output is correct
18 Correct 1314 ms 160664 KB Output is correct
19 Correct 1323 ms 160732 KB Output is correct
20 Correct 1308 ms 160904 KB Output is correct
21 Correct 1315 ms 160688 KB Output is correct
22 Correct 1295 ms 160776 KB Output is correct
23 Correct 1302 ms 160712 KB Output is correct
24 Correct 1414 ms 160656 KB Output is correct
25 Correct 1460 ms 162692 KB Output is correct
26 Correct 1405 ms 160680 KB Output is correct
27 Correct 4276 ms 160996 KB Output is correct
28 Correct 3854 ms 174012 KB Output is correct
29 Correct 3696 ms 174056 KB Output is correct
30 Correct 3790 ms 174260 KB Output is correct
31 Correct 3847 ms 178128 KB Output is correct
32 Correct 1337 ms 160624 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1885 ms 160956 KB Output is correct
2 Correct 1798 ms 160968 KB Output is correct
3 Correct 1760 ms 161012 KB Output is correct
4 Correct 1880 ms 160888 KB Output is correct
5 Correct 2021 ms 160972 KB Output is correct
6 Correct 4022 ms 172536 KB Output is correct
7 Correct 4252 ms 172460 KB Output is correct
8 Correct 3952 ms 172480 KB Output is correct
9 Correct 3951 ms 173832 KB Output is correct
10 Correct 4133 ms 168492 KB Output is correct
11 Correct 4344 ms 168528 KB Output is correct
12 Correct 4101 ms 171288 KB Output is correct
13 Correct 3890 ms 168528 KB Output is correct
14 Correct 3851 ms 168524 KB Output is correct
15 Correct 1551 ms 175564 KB Output is correct
16 Correct 4275 ms 183296 KB Output is correct
17 Correct 1352 ms 160660 KB Output is correct
18 Correct 1426 ms 160652 KB Output is correct
19 Correct 1394 ms 160620 KB Output is correct
20 Correct 1301 ms 160724 KB Output is correct
21 Correct 1356 ms 160672 KB Output is correct
22 Correct 1336 ms 160688 KB Output is correct
23 Correct 1350 ms 160620 KB Output is correct
24 Correct 1308 ms 160820 KB Output is correct
25 Correct 1316 ms 160812 KB Output is correct
26 Correct 1376 ms 160720 KB Output is correct
27 Correct 1408 ms 163040 KB Output is correct
28 Correct 1322 ms 160724 KB Output is correct
29 Correct 3694 ms 161056 KB Output is correct
30 Correct 3756 ms 176612 KB Output is correct
31 Correct 3682 ms 180804 KB Output is correct
32 Correct 3541 ms 180768 KB Output is correct
33 Correct 3801 ms 174164 KB Output is correct
34 Correct 3668 ms 178164 KB Output is correct
35 Correct 3690 ms 174140 KB Output is correct
36 Correct 4715 ms 178068 KB Output is correct
37 Correct 4008 ms 178208 KB Output is correct
38 Correct 3866 ms 181384 KB Output is correct
39 Correct 1450 ms 160656 KB Output is correct
40 Correct 4183 ms 178480 KB Output is correct