oj.uz

Submission #786874

# Submission time Handle Problem Language Result Execution time Memory
786874 2023-07-18T14:07:23 Z drdilyor Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 16900 KB 
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#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 106 ms 8276 KB Output is correct
2 Correct 88 ms 8276 KB Output is correct
3 Correct 143 ms 9816 KB Output is correct
4 Correct 93 ms 8276 KB Output is correct
5 Correct 90 ms 8276 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 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 1 ms 468 KB Output is correct
2 Correct 1 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 468 KB Output is correct
7 Correct 1 ms 544 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 53 ms 1420 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 10 ms 724 KB Output is correct
2 Correct 15 ms 800 KB Output is correct
3 Correct 16 ms 796 KB Output is correct
4 Correct 15 ms 800 KB Output is correct
5 Correct 16 ms 800 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 9 ms 792 KB Output is correct
10 Correct 0 ms 468 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 16096 KB Output is correct
2 Correct 239 ms 16096 KB Output is correct
3 Correct 242 ms 16096 KB Output is correct
4 Correct 269 ms 16812 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 724 KB Output is correct
2 Correct 15 ms 800 KB Output is correct
3 Correct 17 ms 724 KB Output is correct
4 Correct 16 ms 796 KB Output is correct
5 Correct 16 ms 796 KB Output is correct
6 Correct 245 ms 16104 KB Output is correct
7 Correct 238 ms 16104 KB Output is correct
8 Correct 237 ms 16096 KB Output is correct
9 Correct 279 ms 16900 KB Output is correct
10 Correct 92 ms 8276 KB Output is correct
11 Correct 89 ms 8280 KB Output is correct
12 Correct 145 ms 9812 KB Output is correct
13 Correct 94 ms 8280 KB Output is correct
14 Correct 88 ms 8276 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 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 59 ms 1484 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 9 ms 796 KB Output is correct
28 Execution timed out 20064 ms 16108 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 724 KB Output is correct
2 Correct 16 ms 804 KB Output is correct
3 Correct 16 ms 804 KB Output is correct
4 Correct 16 ms 796 KB Output is correct
5 Correct 18 ms 800 KB Output is correct
6 Correct 251 ms 16008 KB Output is correct
7 Correct 239 ms 16084 KB Output is correct
8 Correct 238 ms 16104 KB Output is correct
9 Correct 301 ms 16884 KB Output is correct
10 Correct 91 ms 8280 KB Output is correct
11 Correct 89 ms 8276 KB Output is correct
12 Correct 144 ms 9852 KB Output is correct
13 Correct 101 ms 8276 KB Output is correct
14 Correct 94 ms 8276 KB Output is correct
15 Correct 215 ms 16092 KB Output is correct
16 Execution timed out 20027 ms 16244 KB Time limit exceeded
17 Halted 0 ms 0 KB -