oj.uz

Submission #1067891

# Submission time Handle Problem Language Result Execution time Memory
1067891 2024-08-21T05:21:35 Z 12345678 Wombats (IOI13_wombats) C++17
55 / 100
 15087 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);
            /*
            cout<<"build "<<row<<'\n';
            for (int i=0; i<c; i++){
            for (int j=0; j<c; j++) cout<<mat[i][j]<<' ';
            cout<<'\n';}
            */
        }
    } d[4*nx];
    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);
    /*
    for (int i=0; i<c; i++)
    {
        cout<<"mat ";
        for (int j=0; j<c; j++) cout<<s.d[1].mat[i][j]<<' ';
        cout<<'\n';
    }
    */
}

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 19 ms 77912 KB Output is correct
2 Correct 20 ms 80036 KB Output is correct
3 Correct 54 ms 81492 KB Output is correct
4 Correct 22 ms 79964 KB Output is correct
5 Correct 18 ms 77912 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 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 1 ms 8540 KB Output is correct
6 Correct 2 ms 8636 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8664 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 54 ms 10996 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 19016 KB Output is correct
2 Correct 627 ms 19016 KB Output is correct
3 Correct 550 ms 18772 KB Output is correct
4 Correct 639 ms 18768 KB Output is correct
5 Correct 584 ms 19252 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 2662 ms 16140 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 84368 KB Output is correct
2 Correct 22 ms 82524 KB Output is correct
3 Correct 23 ms 82740 KB Output is correct
4 Correct 49 ms 83500 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 18768 KB Output is correct
2 Correct 572 ms 19004 KB Output is correct
3 Correct 635 ms 19012 KB Output is correct
4 Correct 588 ms 19008 KB Output is correct
5 Correct 623 ms 19000 KB Output is correct
6 Correct 21 ms 84572 KB Output is correct
7 Correct 27 ms 82624 KB Output is correct
8 Correct 22 ms 82656 KB Output is correct
9 Correct 45 ms 85232 KB Output is correct
10 Correct 19 ms 78028 KB Output is correct
11 Correct 26 ms 79964 KB Output is correct
12 Correct 66 ms 81612 KB Output is correct
13 Correct 24 ms 77916 KB Output is correct
14 Correct 18 ms 79964 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 1 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 1 ms 8540 KB Output is correct
25 Correct 49 ms 10876 KB Output is correct
26 Correct 1 ms 8536 KB Output is correct
27 Correct 2641 ms 19092 KB Output is correct
28 Runtime error 2282 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 673 ms 19012 KB Output is correct
2 Correct 591 ms 19004 KB Output is correct
3 Correct 639 ms 18768 KB Output is correct
4 Correct 633 ms 19012 KB Output is correct
5 Correct 606 ms 18772 KB Output is correct
6 Correct 23 ms 86364 KB Output is correct
7 Correct 29 ms 80660 KB Output is correct
8 Correct 21 ms 78684 KB Output is correct
9 Correct 45 ms 87172 KB Output is correct
10 Correct 20 ms 74076 KB Output is correct
11 Correct 21 ms 79964 KB Output is correct
12 Correct 66 ms 83516 KB Output is correct
13 Correct 19 ms 81820 KB Output is correct
14 Correct 21 ms 81812 KB Output is correct
15 Runtime error 15087 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -