oj.uz

답안 #609146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609146 2022-07-27T12:28:46 Z MohamedFaresNebili 웜뱃 (IOI13_wombats) C++14
100 / 100
 12510 ms 174048 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimize("unroll-loops")

            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

# 결과 실행 시간 메모리 Grader output
1 Correct 8854 ms 168536 KB Output is correct
2 Correct 9213 ms 168528 KB Output is correct
3 Correct 9093 ms 171296 KB Output is correct
4 Correct 8974 ms 168528 KB Output is correct
5 Correct 9176 ms 168520 KB Output is correct
6 Correct 3168 ms 160576 KB Output is correct
7 Correct 3163 ms 160628 KB Output is correct
8 Correct 3133 ms 160668 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3174 ms 160584 KB Output is correct
2 Correct 3182 ms 160572 KB Output is correct
3 Correct 3129 ms 160624 KB Output is correct
4 Correct 3119 ms 160640 KB Output is correct
5 Correct 3176 ms 160728 KB Output is correct
6 Correct 3250 ms 160624 KB Output is correct
7 Correct 3285 ms 160728 KB Output is correct
8 Correct 3238 ms 160652 KB Output is correct
9 Correct 3347 ms 160664 KB Output is correct
10 Correct 3475 ms 160832 KB Output is correct
11 Correct 3426 ms 163060 KB Output is correct
12 Correct 3592 ms 160640 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4661 ms 160896 KB Output is correct
2 Correct 4667 ms 160988 KB Output is correct
3 Correct 4508 ms 160996 KB Output is correct
4 Correct 4581 ms 161148 KB Output is correct
5 Correct 4467 ms 161056 KB Output is correct
6 Correct 3284 ms 160676 KB Output is correct
7 Correct 3299 ms 160656 KB Output is correct
8 Correct 3297 ms 160612 KB Output is correct
9 Correct 9710 ms 161056 KB Output is correct
10 Correct 3321 ms 160616 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9915 ms 172480 KB Output is correct
2 Correct 9171 ms 172460 KB Output is correct
3 Correct 9549 ms 172408 KB Output is correct
4 Correct 9350 ms 173200 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4571 ms 160928 KB Output is correct
2 Correct 4664 ms 160920 KB Output is correct
3 Correct 4599 ms 160864 KB Output is correct
4 Correct 4840 ms 160920 KB Output is correct
5 Correct 4789 ms 160916 KB Output is correct
6 Correct 9436 ms 172512 KB Output is correct
7 Correct 9250 ms 172376 KB Output is correct
8 Correct 11065 ms 172404 KB Output is correct
9 Correct 9693 ms 173128 KB Output is correct
10 Correct 9439 ms 168496 KB Output is correct
11 Correct 10647 ms 168496 KB Output is correct
12 Correct 10010 ms 170028 KB Output is correct
13 Correct 9872 ms 168488 KB Output is correct
14 Correct 12510 ms 168496 KB Output is correct
15 Correct 3882 ms 160580 KB Output is correct
16 Correct 4032 ms 160568 KB Output is correct
17 Correct 3304 ms 160648 KB Output is correct
18 Correct 3363 ms 160736 KB Output is correct
19 Correct 3270 ms 160720 KB Output is correct
20 Correct 3346 ms 160700 KB Output is correct
21 Correct 3349 ms 160736 KB Output is correct
22 Correct 3367 ms 160656 KB Output is correct
23 Correct 3385 ms 160676 KB Output is correct
24 Correct 3351 ms 160696 KB Output is correct
25 Correct 3385 ms 161964 KB Output is correct
26 Correct 3285 ms 160740 KB Output is correct
27 Correct 10774 ms 160992 KB Output is correct
28 Correct 9995 ms 173112 KB Output is correct
29 Correct 9679 ms 171096 KB Output is correct
30 Correct 9331 ms 170924 KB Output is correct
31 Correct 9143 ms 174048 KB Output is correct
32 Correct 3210 ms 160588 KB Output is correct

Subtask #6
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4600 ms 160996 KB Output is correct
2 Correct 4356 ms 160952 KB Output is correct
3 Correct 4313 ms 160996 KB Output is correct
4 Correct 4317 ms 161000 KB Output is correct
5 Correct 4294 ms 161016 KB Output is correct
6 Correct 9041 ms 172512 KB Output is correct
7 Correct 8887 ms 172404 KB Output is correct
8 Correct 8984 ms 172404 KB Output is correct
9 Correct 8913 ms 173200 KB Output is correct
10 Correct 8935 ms 168532 KB Output is correct
11 Correct 9352 ms 168492 KB Output is correct
12 Correct 9585 ms 170028 KB Output is correct
13 Correct 8928 ms 168500 KB Output is correct
14 Correct 8945 ms 168396 KB Output is correct
15 Correct 3372 ms 172372 KB Output is correct
16 Correct 9241 ms 173992 KB Output is correct
17 Correct 3161 ms 160616 KB Output is correct
18 Correct 3126 ms 160628 KB Output is correct
19 Correct 3294 ms 160592 KB Output is correct
20 Correct 3267 ms 160668 KB Output is correct
21 Correct 3119 ms 160708 KB Output is correct
22 Correct 3152 ms 160812 KB Output is correct
23 Correct 3207 ms 160680 KB Output is correct
24 Correct 3439 ms 160704 KB Output is correct
25 Correct 3327 ms 160840 KB Output is correct
26 Correct 3288 ms 160696 KB Output is correct
27 Correct 3272 ms 161668 KB Output is correct
28 Correct 3309 ms 160668 KB Output is correct
29 Correct 9558 ms 160916 KB Output is correct
30 Correct 9321 ms 172932 KB Output is correct
31 Correct 8856 ms 173052 KB Output is correct
32 Correct 9351 ms 173056 KB Output is correct
33 Correct 9097 ms 170880 KB Output is correct
34 Correct 9356 ms 171100 KB Output is correct
35 Correct 9044 ms 170708 KB Output is correct
36 Correct 9955 ms 171064 KB Output is correct
37 Correct 9475 ms 173976 KB Output is correct
38 Correct 8634 ms 173872 KB Output is correct
39 Correct 3422 ms 160616 KB Output is correct
40 Correct 11616 ms 171116 KB Output is correct