oj.uz

Submission #608819

# Submission time Handle Problem Language Result Execution time Memory
608819 2022-07-27T10:29:02 Z MohamedFaresNebili Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 30332 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, C, H[5000][200], K[5000][200], DP[100][100];
            void precomputation(int i) {
                priority_queue<pi, vector<pi>, greater<pi>> pq;
                pq.push({0, {0, i}}); vector<vector<int>> D;
                D = vector<vector<int>> (R, vector<int>(C, oo));
                vector<vector<bool>> vis(R, vector<bool>(C, 0));
                D[0][i] = 0;
                while(!pq.empty()) {
                    int U = pq.top().ss.ff, V = pq.top().ss.ss;
                    int W = pq.top().ff; pq.pop();
                    if(W != D[U][V] || vis[U][V]) continue;
                    vis[U][V] = 1;
                    if(V < C - 1) {
                        if(!vis[U][V + 1] && D[U][V + 1] > D[U][V] + H[U][V]) {
                            D[U][V + 1] = D[U][V] + H[U][V];
                            pq.push({D[U][V + 1], {U, V + 1}});
                        }
                    }
                    if(V > 0) {
                        if(!vis[U][V - 1] && D[U][V - 1] > D[U][V] + H[U][V - 1]) {
                            D[U][V - 1] = D[U][V] + H[U][V - 1];
                            pq.push({D[U][V - 1], {U, V - 1}});
                        }
                    }
                    if(U < R - 1) {
                        if(!vis[U + 1][V] && D[U + 1][V] > D[U][V] + K[U][V]) {
                            D[U + 1][V] = D[U][V] + K[U][V];
                            pq.push({D[U + 1][V], {U + 1, V}});
                        }
                    }
                }
                for(int l = 0; l < C; l++)
                    DP[i][l] = D[R - 1][l];
            }
            void init(int r, int c, int h[5000][200], int v[5000][200]) {
                R = r, C = c;
                for(int l = 0; l < R; l++)
                    for(int i = 0; i < C; i++)
                        H[l][i] = h[l][i],
                        K[l][i] = v[l][i];
                for(int l = 0; l < C; l++) precomputation(l);
            }

            void changeH(int P, int Q, int W) {
                H[P][Q] = W;
                if(C <= 20) for(int l = 0; l < C; l++) precomputation(l);
            }
            void changeV(int P, int Q, int W) {
                K[P][Q] = W;
                if(C <= 20) for(int l = 0; l < C; l++) precomputation(l);
            }

            int escape(int V1, int V2) {
                if(C > 20) precomputation(V1);
                return DP[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 267 ms 12688 KB Output is correct
2 Correct 268 ms 12700 KB Output is correct
3 Correct 357 ms 14196 KB Output is correct
4 Correct 260 ms 12688 KB Output is correct
5 Correct 278 ms 12688 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 63 ms 1388 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 848 KB Output is correct
2 Correct 444 ms 960 KB Output is correct
3 Correct 287 ms 732 KB Output is correct
4 Correct 285 ms 728 KB Output is correct
5 Correct 273 ms 704 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 458 ms 732 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 16564 KB Output is correct
2 Correct 1698 ms 16596 KB Output is correct
3 Correct 939 ms 16568 KB Output is correct
4 Correct 946 ms 17360 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 724 KB Output is correct
2 Correct 497 ms 980 KB Output is correct
3 Correct 268 ms 720 KB Output is correct
4 Correct 271 ms 844 KB Output is correct
5 Correct 267 ms 728 KB Output is correct
6 Correct 858 ms 16564 KB Output is correct
7 Correct 1493 ms 16612 KB Output is correct
8 Correct 847 ms 16580 KB Output is correct
9 Correct 925 ms 17596 KB Output is correct
10 Correct 291 ms 12688 KB Output is correct
11 Correct 260 ms 12688 KB Output is correct
12 Correct 310 ms 15460 KB Output is correct
13 Correct 245 ms 12692 KB Output is correct
14 Correct 249 ms 12712 KB Output is correct
15 Correct 1 ms 368 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 312 KB Output is correct
25 Correct 63 ms 2672 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 410 ms 844 KB Output is correct
28 Execution timed out 20013 ms 22204 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 844 KB Output is correct
2 Correct 450 ms 1096 KB Output is correct
3 Correct 269 ms 716 KB Output is correct
4 Correct 268 ms 728 KB Output is correct
5 Correct 267 ms 716 KB Output is correct
6 Correct 871 ms 16568 KB Output is correct
7 Correct 1472 ms 16604 KB Output is correct
8 Correct 865 ms 16596 KB Output is correct
9 Correct 904 ms 17756 KB Output is correct
10 Correct 266 ms 12688 KB Output is correct
11 Correct 262 ms 12796 KB Output is correct
12 Correct 320 ms 15472 KB Output is correct
13 Correct 270 ms 12688 KB Output is correct
14 Correct 249 ms 12688 KB Output is correct
15 Incorrect 10310 ms 30332 KB Output isn't correct
16 Halted 0 ms 0 KB -