oj.uz

Submission #608773

# Submission time Handle Problem Language Result Execution time Memory
608773 2022-07-27T10:00:51 Z MohamedFaresNebili Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 16452 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>;
 
            #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], cur;
            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],
              			cur += K[l][i];
            }
 
            void changeH(int P, int Q, int W) { H[P][Q] = W; }
            void changeV(int P, int Q, int W) {
                cur -= K[P][Q] - W; K[P][Q] = W; 
            }
 
            using pi = pair<int, pair<int, int>>;
 
            int escape(int V1, int V2) {
                if(C == 1)
                    return cur;
                priority_queue<pi, vector<pi>, greater<pi>> pq;
                pq.push({0, {0, V1}}); vector<vector<int>> D;
                D = vector<vector<int>> (R, vector<int>(C, oo));
                D[0][V1] = 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]) continue;
                    if(V < C - 1) {
                        if(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(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(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}});
                        }
                    }
                }
                return D[R - 1][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 7 ms 11988 KB Output is correct
2 Correct 8 ms 11984 KB Output is correct
3 Correct 84 ms 13640 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11936 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 26 ms 340 KB Output is correct
5 Correct 10 ms 340 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 20 ms 340 KB Output is correct
8 Correct 13 ms 396 KB Output is correct
9 Correct 15 ms 388 KB Output is correct
10 Correct 18 ms 340 KB Output is correct
11 Correct 7692 ms 1364 KB Output is correct
12 Correct 22 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 672 KB Output is correct
2 Correct 201 ms 840 KB Output is correct
3 Correct 130 ms 600 KB Output is correct
4 Correct 129 ms 676 KB Output is correct
5 Correct 122 ms 596 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 188 ms 724 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 16208 KB Output is correct
2 Correct 1288 ms 16224 KB Output is correct
3 Correct 645 ms 16216 KB Output is correct
4 Execution timed out 20063 ms 16416 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 684 KB Output is correct
2 Correct 206 ms 852 KB Output is correct
3 Correct 122 ms 676 KB Output is correct
4 Correct 123 ms 596 KB Output is correct
5 Correct 122 ms 724 KB Output is correct
6 Correct 613 ms 16336 KB Output is correct
7 Correct 1275 ms 16224 KB Output is correct
8 Correct 611 ms 16232 KB Output is correct
9 Execution timed out 20095 ms 16392 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 596 KB Output is correct
2 Correct 207 ms 860 KB Output is correct
3 Correct 121 ms 596 KB Output is correct
4 Correct 133 ms 680 KB Output is correct
5 Correct 133 ms 672 KB Output is correct
6 Correct 662 ms 16212 KB Output is correct
7 Correct 1221 ms 16220 KB Output is correct
8 Correct 605 ms 16212 KB Output is correct
9 Execution timed out 20053 ms 16452 KB Time limit exceeded
10 Halted 0 ms 0 KB -