oj.uz

Submission #786876

# Submission time Handle Problem Language Result Execution time Memory
786876 2023-07-18T14:08:24 Z drdilyor Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 16848 KB 
#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
using ll = long long;
const int inf = 1e9 + 1000;


int r, c;
int level[5000][200];
int pass[5000][200];
int dist[200][200];

vector<char> dirty;

void update(int v2) {
    if (!dirty[v2]) return;
    dirty[v2] = 0;

    vector<int> dp(c, inf);
    dp[v2] = 0;
    for (int i = r-1; i >= 0; i--) {

        auto sum = [&](int r) {
            if (r < 0) return 0;
            return level[i][r];
        };

        vector<int> ndp(dp);

        int mn = inf;
        for (int j = 0; j < c; j++) {
            ndp[j] = min(ndp[j], mn + sum(j-1));
            mn = min(mn, dp[j] - sum(j-1));
        }

        mn = inf;
        for (int j = c-1; j >= 0; j--) {
            ndp[j] = min(ndp[j], mn - sum(j-1));
            mn = min(mn, dp[j] + sum(j-1));
        }

        for (int j = 0; j < c; j++) {
            if (i) ndp[j] += pass[i-1][j];
        }

        dp.swap(ndp);
    }
    for (int v1 = 0; v1 < c; v1++)
        dist[v1][v2] = dp[v1];
}

void init(int32_t r, int32_t c, int32_t h[5000][200], int32_t v[5000][200]) {
    ::r = r;
    ::c = c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c-1; j++) {
            level[i][j] = h[i][j];
            if (j) level[i][j] += level[i][j-1];
        }
    }

    for (int i = 0; i < r-1; i++) {
        for (int j = 0; j < c; j++) {
            pass[i][j] =v[i][j];
        }
    }
    dirty.assign(c, 1);
    memset(dist, 0, sizeof(dist));
}

void changeH(int32_t p, int32_t q, int32_t w) {
    int actual = level[p][q];
    if (q) actual -= level[p][q-1];
    int diff = w - actual;
    for (int i = q; i < c-1; i++)
        level[p][i] += diff;
    dirty.assign(c, 1);
}

void changeV(int32_t p, int32_t q, int32_t w) {
    pass[p][q] = w;
    dirty.assign(c, 1);
}

int32_t escape(int32_t v1, int32_t v2) {
    update(v2);
    return dist[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 40 ms 8276 KB Output is correct
2 Correct 41 ms 8276 KB Output is correct
3 Correct 92 ms 9832 KB Output is correct
4 Correct 41 ms 8304 KB Output is correct
5 Correct 46 ms 8284 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 66 ms 1504 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 7 ms 800 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 4 ms 800 KB Output is correct
10 Correct 1 ms 388 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16100 KB Output is correct
2 Correct 133 ms 16096 KB Output is correct
3 Correct 120 ms 16096 KB Output is correct
4 Correct 155 ms 16832 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 7 ms 796 KB Output is correct
4 Correct 11 ms 728 KB Output is correct
5 Correct 10 ms 724 KB Output is correct
6 Correct 179 ms 16084 KB Output is correct
7 Correct 113 ms 16112 KB Output is correct
8 Correct 114 ms 16084 KB Output is correct
9 Correct 159 ms 16808 KB Output is correct
10 Correct 40 ms 8280 KB Output is correct
11 Correct 42 ms 8276 KB Output is correct
12 Correct 92 ms 9824 KB Output is correct
13 Correct 39 ms 8276 KB Output is correct
14 Correct 40 ms 8276 KB Output is correct
15 Correct 0 ms 480 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 0 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 57 ms 1508 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 4 ms 724 KB Output is correct
28 Execution timed out 20045 ms 16256 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 5 ms 724 KB Output is correct
3 Correct 10 ms 724 KB Output is correct
4 Correct 10 ms 800 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 113 ms 15988 KB Output is correct
7 Correct 139 ms 16096 KB Output is correct
8 Correct 153 ms 16084 KB Output is correct
9 Correct 156 ms 16848 KB Output is correct
10 Correct 56 ms 8280 KB Output is correct
11 Correct 41 ms 8276 KB Output is correct
12 Correct 97 ms 9892 KB Output is correct
13 Correct 39 ms 8276 KB Output is correct
14 Correct 53 ms 8276 KB Output is correct
15 Correct 155 ms 16008 KB Output is correct
16 Execution timed out 20025 ms 16124 KB Time limit exceeded
17 Halted 0 ms 0 KB -