oj.uz

Submission #944177

# Submission time Handle Problem Language Result Execution time Memory
944177 2024-03-12T09:36:06 Z wii Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 18856 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];
struct comp {
    bool operator() (int a, int b) {
        return tmp[a] < tmp[b];
    }
};

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

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

        while (!q.empty()) {
            auto u = *q.begin(); q.erase(q.begin());
            int w = tmp[u];

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

            if (u > 0) {
                if (minimize(tmp[u - 1], tmp[u] + h[i][u - 1]))
                    q.emplace(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;
      |      ^~~
wombats.cpp: In function 'void bfs(int)':
wombats.cpp:41:17: warning: unused variable 'w' [-Wunused-variable]
   41 |             int w = tmp[u];
      |                 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 12904 KB Output is correct
2 Correct 80 ms 12912 KB Output is correct
3 Correct 132 ms 14420 KB Output is correct
4 Correct 84 ms 12888 KB Output is correct
5 Correct 80 ms 12892 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 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 8676 KB Output is correct
11 Correct 63 ms 9428 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8873 ms 8708 KB Output is correct
2 Correct 8106 ms 8712 KB Output is correct
3 Correct 8832 ms 8712 KB Output is correct
4 Correct 8875 ms 8712 KB Output is correct
5 Correct 8679 ms 8716 KB Output is correct
6 Correct 1 ms 4596 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Execution timed out 20056 ms 8708 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 18060 KB Output is correct
2 Correct 449 ms 18256 KB Output is correct
3 Correct 381 ms 18208 KB Output is correct
4 Correct 455 ms 18772 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8739 ms 8712 KB Output is correct
2 Correct 7856 ms 8712 KB Output is correct
3 Correct 8869 ms 8712 KB Output is correct
4 Correct 8897 ms 8708 KB Output is correct
5 Correct 8759 ms 8708 KB Output is correct
6 Correct 399 ms 18060 KB Output is correct
7 Correct 467 ms 18056 KB Output is correct
8 Correct 433 ms 18012 KB Output is correct
9 Correct 408 ms 18768 KB Output is correct
10 Correct 83 ms 12904 KB Output is correct
11 Correct 88 ms 12908 KB Output is correct
12 Correct 135 ms 14440 KB Output is correct
13 Correct 82 ms 12892 KB Output is correct
14 Correct 80 ms 12908 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4440 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 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 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8536 KB Output is correct
25 Correct 55 ms 9496 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Execution timed out 20088 ms 8708 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8878 ms 8712 KB Output is correct
2 Correct 7885 ms 8712 KB Output is correct
3 Correct 8803 ms 8712 KB Output is correct
4 Correct 8901 ms 8712 KB Output is correct
5 Correct 8488 ms 8712 KB Output is correct
6 Correct 388 ms 18056 KB Output is correct
7 Correct 433 ms 18008 KB Output is correct
8 Correct 390 ms 18312 KB Output is correct
9 Correct 409 ms 18856 KB Output is correct
10 Correct 84 ms 12908 KB Output is correct
11 Correct 86 ms 12888 KB Output is correct
12 Correct 133 ms 14268 KB Output is correct
13 Correct 88 ms 13140 KB Output is correct
14 Correct 82 ms 12888 KB Output is correct
15 Execution timed out 20057 ms 18060 KB Time limit exceeded
16 Halted 0 ms 0 KB -