oj.uz

Submission #944173

# Submission time Handle Problem Language Result Execution time Memory
944173 2024-03-12T09:31:00 Z wii Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 27828 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int MaxR = 5000 + 2;
const int MaxC = 200 + 2;
const int Inf = 0x3f3f3f3f;

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

void init(int R, int C, int H[5000][200], int V[5000][200]);
void changeH(int P, int Q, int W);
void changeV(int P, int Q, int W);
int escape(int V1, int V2);

int r, c;
int h[MaxR][MaxC];
int v[MaxR][MaxC];
int dp[MaxR][MaxC];

int tmp[MaxC];
void bfs(int u) {
    for (int i = 0; i < c; ++i)
        tmp[i] = Inf;
    tmp[u] = 0;

    for (int i = 0; i < r; ++i) {
        priority_queue<pair<int, int>> q;
        for (int j = 0; j < c; ++j) if (tmp[j] != Inf)
            q.emplace(-tmp[j], j);

        while (!q.empty()) {
            auto [w, u] = q.top(); q.pop();
            w = -w;

            if (u + 1 < c) {
                if (minimize(tmp[u + 1], tmp[u] + h[i][u]))
                    q.emplace(-tmp[u + 1], u + 1);
            }

            if (u > 0) {
                if (minimize(tmp[u - 1], tmp[u] + h[i][u - 1]))
                    q.emplace(-tmp[u - 1], u - 1);
            }
        }



        if (i + 1 < r)
        for (int j = 0; j < c; ++j)
            tmp[j] += v[i][j];
    }

    for (int j = 0; j < c; ++j)
        dp[u][j] = tmp[j];
}

void build() {
    for (int i = 0; i < c; ++i) {
        bfs(i);
    }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    build();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    build();
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;

    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 - 1 < r; ++i)
        for (int j = 0; j < c; ++j)
            v[i][j] = V[i][j];

   build();
}

int escape(int V1, int V2) {
    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 62 ms 12892 KB Output is correct
2 Correct 75 ms 12888 KB Output is correct
3 Correct 115 ms 15696 KB Output is correct
4 Correct 62 ms 12940 KB Output is correct
5 Correct 64 ms 12888 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 69 ms 10864 KB Output is correct
12 Correct 2 ms 8536 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8477 ms 8792 KB Output is correct
2 Correct 5225 ms 8796 KB Output is correct
3 Correct 8365 ms 8796 KB Output is correct
4 Correct 8467 ms 8792 KB Output is correct
5 Correct 8328 ms 8796 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Execution timed out 20010 ms 8796 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 18264 KB Output is correct
2 Correct 313 ms 18116 KB Output is correct
3 Correct 356 ms 18128 KB Output is correct
4 Correct 333 ms 19284 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8439 ms 8792 KB Output is correct
2 Correct 5119 ms 8792 KB Output is correct
3 Correct 8383 ms 8800 KB Output is correct
4 Correct 8454 ms 8796 KB Output is correct
5 Correct 8194 ms 9040 KB Output is correct
6 Correct 309 ms 18132 KB Output is correct
7 Correct 314 ms 18364 KB Output is correct
8 Correct 304 ms 18012 KB Output is correct
9 Correct 332 ms 19280 KB Output is correct
10 Correct 62 ms 12928 KB Output is correct
11 Correct 61 ms 13144 KB Output is correct
12 Correct 114 ms 15596 KB Output is correct
13 Correct 61 ms 12892 KB Output is correct
14 Correct 65 ms 12888 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4696 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8676 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 55 ms 10832 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Execution timed out 20055 ms 8716 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8456 ms 8804 KB Output is correct
2 Correct 5158 ms 8792 KB Output is correct
3 Correct 8378 ms 8800 KB Output is correct
4 Correct 8527 ms 8796 KB Output is correct
5 Correct 8232 ms 8788 KB Output is correct
6 Correct 303 ms 18136 KB Output is correct
7 Correct 317 ms 18264 KB Output is correct
8 Correct 302 ms 18132 KB Output is correct
9 Correct 335 ms 19300 KB Output is correct
10 Correct 62 ms 12928 KB Output is correct
11 Correct 62 ms 12940 KB Output is correct
12 Correct 114 ms 15596 KB Output is correct
13 Correct 63 ms 12888 KB Output is correct
14 Correct 62 ms 12888 KB Output is correct
15 Execution timed out 20030 ms 27828 KB Time limit exceeded
16 Halted 0 ms 0 KB -