oj.uz

Submission #276089

# Submission time Handle Problem Language Result Execution time Memory
276089 2020-08-20T10:41:33 Z MKopchev Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 104268 KB 
#include<bits/stdc++.h>
#include"wombats.h"
using namespace std;
const int rmax=5e3+5,cmax=2e2+5,block_size=10,inf=1e9;
int r,c,h[rmax][cmax],v[rmax][cmax];

int tree[(1<<10)+42][cmax][cmax];

int current[cmax][cmax],help[cmax][cmax];

int pref[cmax];

void make_block(int which)
{
    for(int j=0;j<c;j++)
        for(int k=0;k<c;k++)
            if(j==k)current[j][k]=0;
            else current[j][k]=inf;

    int start=which*block_size,stop=min(r-1,which*block_size+block_size-1);

    for(int i=start;i<=stop;i++)
    {
        for(int j=0;j<c;j++)
            for(int k=0;k<c;k++)
                help[j][k]=inf;

        for(int j=0;j<c;j++)
            pref[j+1]=pref[j]+h[i][j];

        for(int j=0;j<c;j++)
            for(int k=0;k<c;k++)
                for(int p=0;p<c;p++)
                {
                    int cur=current[j][p];

                    cur=cur+abs(pref[p]-pref[k]);

                    if(i!=start)cur+=v[i-1][p];

                    //cout<<j<<" "<<k<<" "<<p<<" -> "<<cur<<" "<<abs(pref[p]-pref[k])<<" "<<current[j][p]<<endl;

                    help[j][k]=min(help[j][k],cur);
                }

        for(int j=0;j<c;j++)
            for(int k=0;k<c;k++)
                current[j][k]=help[j][k];
        /*
        cout<<start<<" "<<i<<endl;
        for(int j=0;j<c;j++)
        {
            for(int k=0;k<c;k++)cout<<current[j][k]<<" ";
            cout<<endl;
        }
        cout<<"---"<<endl;
        */
    }
}

void build(int node,int l,int r,int pos)
{
    if(l==r)
    {
        for(int j=0;j<c;j++)
            for(int k=0;k<c;k++)
                tree[node][j][k]=current[j][k];
        return;
    }

    int av=(l+r)/2;

    if(pos<=av)build(node*2,l,av,pos);
    else build(node*2+1,av+1,r,pos);

    for(int j=0;j<c;j++)
        for(int k=0;k<c;k++)
        {
            tree[node][j][k]=inf;
            for(int p=0;p<c;p++)
                tree[node][j][k]=min(tree[node][j][k],tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k]);
        }

}
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<R-1;i++)
        for(int j=0;j<C;j++)
        v[i][j]=V[i][j];

    for(int i=0;i*block_size<r;i++)
    {
        make_block(i);
        build(1,0,(r-1)/block_size,i);
    }
}

void changeH(int P,int Q,int W)
{
    h[P][Q]=W;
    make_block(P/block_size);

    build(1,0,(r-1)/block_size,P/block_size);
}
void changeV(int P,int Q,int W)
{
    v[P][Q]=W;
    make_block(P/block_size);

    build(1,0,(r-1)/block_size,P/block_size);
}

int escape(int V1,int V2)
{
    return tree[1][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 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 97 ms 15352 KB Output is correct
4 Correct 9 ms 12672 KB Output is correct
5 Correct 9 ms 12672 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 97 ms 2936 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2206 ms 2544 KB Output is correct
2 Correct 2272 ms 2532 KB Output is correct
3 Correct 2310 ms 2572 KB Output is correct
4 Correct 2327 ms 2680 KB Output is correct
5 Correct 2321 ms 2552 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 11180 ms 2568 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21376 KB Output is correct
2 Correct 16 ms 21376 KB Output is correct
3 Correct 15 ms 21376 KB Output is correct
4 Correct 63 ms 22776 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2243 ms 2552 KB Output is correct
2 Correct 2380 ms 2536 KB Output is correct
3 Correct 2394 ms 2684 KB Output is correct
4 Correct 2380 ms 2752 KB Output is correct
5 Correct 2297 ms 2552 KB Output is correct
6 Correct 15 ms 21376 KB Output is correct
7 Correct 15 ms 21376 KB Output is correct
8 Correct 17 ms 21352 KB Output is correct
9 Correct 58 ms 22784 KB Output is correct
10 Correct 9 ms 12672 KB Output is correct
11 Correct 9 ms 12672 KB Output is correct
12 Correct 96 ms 15352 KB Output is correct
13 Correct 9 ms 12672 KB Output is correct
14 Correct 9 ms 12672 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 512 KB Output is correct
25 Correct 92 ms 3068 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 11069 ms 2568 KB Output is correct
28 Execution timed out 20036 ms 104268 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2198 ms 2568 KB Output is correct
2 Correct 2482 ms 2532 KB Output is correct
3 Correct 2531 ms 2572 KB Output is correct
4 Correct 2524 ms 2496 KB Output is correct
5 Correct 2400 ms 2552 KB Output is correct
6 Correct 15 ms 21376 KB Output is correct
7 Correct 15 ms 21376 KB Output is correct
8 Correct 17 ms 21376 KB Output is correct
9 Correct 66 ms 22740 KB Output is correct
10 Correct 10 ms 12672 KB Output is correct
11 Correct 11 ms 12672 KB Output is correct
12 Correct 130 ms 15352 KB Output is correct
13 Correct 9 ms 12672 KB Output is correct
14 Correct 10 ms 12672 KB Output is correct
15 Execution timed out 20048 ms 54904 KB Time limit exceeded
16 Halted 0 ms 0 KB -