Submission #609146

#	Time	Username	Problem	Language	Result	Execution time	Memory
609146		MohamedFaresNebili	Wombats (IOI13_wombats)	C++14	100 / 100	12510 ms	174048 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 = 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 (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: 21 / 21
• Subtask 6: 24 / 24