Submission #608819

#	Time	Username	Problem	Language	Result	Execution time	Memory
608819		MohamedFaresNebili	Wombats (IOI13_wombats)	C++14	55 / 100	20013 ms	30332 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24