oj.uz

Submission #1067934

# Submission time Handle Problem Language Result Execution time Memory
1067934 2024-08-21T05:45:37 Z 12345678 Wombats (IOI13_wombats) C++17
55 / 100
 15338 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5, cx=1e2+5;

int r, c, ver[nx][cx], qs[nx][cx], dp[nx][cx];

int dist(int row, int a, int b)
{
    if (b>=a) return ver[row][a]+qs[row][b]-qs[row][a];
    else return ver[row][a]+qs[row][a]-qs[row][b];
}

struct segtree
{
    struct matrix
    {
        int mat[cx][cx];
        void build(int row)
        {
            for (int i=0; i<c; i++) for (int j=0; j<c; j++) mat[i][j]=dist(row, j, i);
        }
    } d[16370];
    void merge(int l, int r, int idx)
    {
        for (int i=0; i<c; i++) for (int j=0; j<c; j++) d[idx].mat[i][j]=1e9;
        for (int i=0; i<c; i++) for (int j=0; j<c; j++) for (int k=0; k<c; k++) d[idx].mat[i][j]=min(d[idx].mat[i][j], d[2*idx+1].mat[i][k]+d[2*idx].mat[k][j]);
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i].build(l), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        merge(l, r, i);
    }
    void update(int l, int r, int i, int idx)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i].build(idx), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx);
        update(md+1, r, 2*i+1, idx);
        merge(l, r, i);
    }
} s;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r=R, c=C;
    for (int i=0; i<R-1; i++) for (int j=0; j<C; j++) ver[i+1][j]=V[i][j];
    for (int i=0; i<R; i++) for (int j=0; j<C-1; j++) qs[i][j+1]=H[i][j]+qs[i][j];
    s.build(1, r-1, 1);
}

void changeH(int P, int Q, int W) {
    int lst=qs[P][Q+1]-qs[P][Q];
    int delta=W-lst;
    for (int i=Q+1; i<c; i++) qs[P][i]+=delta;
    if (P>0) s.update(1, r-1, 1, P);
}

void changeV(int P, int Q, int W) {
    ver[P+1][Q]=W;
    s.update(1, r-1, 1, P+1);
}

int escape(int V1, int V2) {
    vector<int> tmp;
    int res=1e9;
    for (int i=0; i<c; i++) res=min(res, s.d[1].mat[V2][i]+dist(0, V1, i));
    return res;
}

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 16 ms 50008 KB Output is correct
2 Correct 18 ms 50012 KB Output is correct
3 Correct 57 ms 53440 KB Output is correct
4 Correct 18 ms 50008 KB Output is correct
5 Correct 17 ms 50008 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 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 45 ms 9472 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 13652 KB Output is correct
2 Correct 578 ms 13392 KB Output is correct
3 Correct 562 ms 13704 KB Output is correct
4 Correct 567 ms 13684 KB Output is correct
5 Correct 537 ms 13544 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
9 Correct 2415 ms 13704 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 58260 KB Output is correct
2 Correct 22 ms 59996 KB Output is correct
3 Correct 18 ms 58204 KB Output is correct
4 Correct 40 ms 60784 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 14948 KB Output is correct
2 Correct 570 ms 13608 KB Output is correct
3 Correct 566 ms 15192 KB Output is correct
4 Correct 556 ms 13648 KB Output is correct
5 Correct 554 ms 15232 KB Output is correct
6 Correct 22 ms 58204 KB Output is correct
7 Correct 20 ms 58200 KB Output is correct
8 Correct 22 ms 59996 KB Output is correct
9 Correct 40 ms 60908 KB Output is correct
10 Correct 19 ms 53852 KB Output is correct
11 Correct 19 ms 55640 KB Output is correct
12 Correct 58 ms 55532 KB Output is correct
13 Correct 19 ms 55640 KB Output is correct
14 Correct 17 ms 53936 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 0 ms 4444 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 42 ms 9520 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 2493 ms 13704 KB Output is correct
28 Runtime error 2266 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 13392 KB Output is correct
2 Correct 548 ms 14928 KB Output is correct
3 Correct 566 ms 15184 KB Output is correct
4 Correct 591 ms 15196 KB Output is correct
5 Correct 535 ms 13648 KB Output is correct
6 Correct 19 ms 59996 KB Output is correct
7 Correct 20 ms 59988 KB Output is correct
8 Correct 21 ms 58200 KB Output is correct
9 Correct 41 ms 59124 KB Output is correct
10 Correct 19 ms 55644 KB Output is correct
11 Correct 17 ms 53948 KB Output is correct
12 Correct 58 ms 57392 KB Output is correct
13 Correct 19 ms 53848 KB Output is correct
14 Correct 18 ms 55644 KB Output is correct
15 Runtime error 15338 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -