oj.uz

Submission #276160

# Submission time Handle Problem Language Result Execution time Memory
276160 2020-08-20T11:14:19 Z MKopchev Wombats (IOI13_wombats) C++14
100 / 100
 12127 ms 192164 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];

int opt[cmax][cmax];

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

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

        cur+=v[i-1][p];

        if(help[j][k]>cur)
        {
            help[j][k]=cur;
            opt[j][k]=p;
        }
    }

    //cout<<"brute_one "<<j<<" "<<k<<" "<<opt[j][k]<<endl;
}

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];

        if(i==start)
        {
            for(int k=0;k<c;k++)
                for(int p=0;p<c;p++)
                    help[k][p]=abs(pref[p]-pref[k]);
        }

        else
        {
        /*
        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]);

                    cur+=v[i-1][p];

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

        memset(opt,-1,sizeof(opt));
        /*
        for(int j=0;j<c;j++)
            for(int k=0;k<c;k++)
                brute_one(i,j,k);
        */

        for(int t=0;t<c;t++)
        {
            brute_one(i,t,0);
            brute_one(i,c-1,t);
        }


        for(int diff=-c;diff<=c;diff++)
        {
            for(int j=0;j<c;j++)
            {
                int k=j+diff;

                if(0<=k&&k<c&&opt[j][k]==-1)
                {
                    //cout<<j<<" "<<k<<endl;

                    assert(opt[j][k-1]!=-1&&opt[j+1][k]!=-1);

                    help[j][k]=inf;

                    for(int p=opt[j][k-1];p<=opt[j+1][k];p++)
                    {
                        int cur=current[j][p];

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

                        cur+=v[i-1][p];

                        if(help[j][k]>cur)
                        {
                            help[j][k]=cur;
                            opt[j][k]=p;
                        }
                    }
                }
            }
        }

        }

        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 brute(int node,int j,int k,int av)
{
    tree[node][j][k]=inf;

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

        //cout<<"cur= "<<cur<<endl;

        if(tree[node][j][k]>cur)
        {
            tree[node][j][k]=cur;
            opt[j][k]=p;
        }
    }

    //cout<<"brute "<<j<<" "<<k<<" "<<opt[j][k]<<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);

    //opt[i][j-1]<=opt[i][j]<=opt[i+1][j]
    /*
    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]);
        }
    */
    memset(opt,-1,sizeof(opt));

    for(int i=0;i<c;i++)
    {
        brute(node,i,0,av);
        brute(node,c-1,i,av);
    }

    for(int diff=-c;diff<=c;diff++)
    {
        for(int j=0;j<c;j++)
        {
            int k=j+diff;

            if(0<=k&&k<c&&opt[j][k]==-1)
            {
                //cout<<j<<" "<<k<<endl;

                assert(opt[j][k-1]!=-1&&opt[j+1][k]!=-1);

                tree[node][j][k]=inf;

                for(int p=opt[j][k-1];p<=opt[j+1][k];p++)
                {
                    int cur=tree[node*2][j][p]+v[av*block_size+block_size-1][p]+tree[node*2+1][p][k];

                    if(tree[node][j][k]>cur)
                    {
                        tree[node][j][k]=cur;
                        opt[j][k]=p;
                    }
                }
            }
        }
    }
}
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 108 ms 12792 KB Output is correct
2 Correct 112 ms 12844 KB Output is correct
3 Correct 218 ms 15608 KB Output is correct
4 Correct 107 ms 12792 KB Output is correct
5 Correct 114 ms 12920 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 115 ms 3216 KB Output is correct
12 Correct 2 ms 744 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 2808 KB Output is correct
2 Correct 207 ms 2708 KB Output is correct
3 Correct 293 ms 2732 KB Output is correct
4 Correct 260 ms 2808 KB Output is correct
5 Correct 268 ms 2812 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 982 ms 2680 KB Output is correct
10 Correct 1 ms 512 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 21624 KB Output is correct
2 Correct 119 ms 21496 KB Output is correct
3 Correct 119 ms 21496 KB Output is correct
4 Correct 156 ms 22904 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 2680 KB Output is correct
2 Correct 199 ms 2808 KB Output is correct
3 Correct 261 ms 2680 KB Output is correct
4 Correct 251 ms 2688 KB Output is correct
5 Correct 254 ms 2680 KB Output is correct
6 Correct 118 ms 21496 KB Output is correct
7 Correct 116 ms 21496 KB Output is correct
8 Correct 116 ms 21632 KB Output is correct
9 Correct 162 ms 23032 KB Output is correct
10 Correct 108 ms 12792 KB Output is correct
11 Correct 131 ms 12920 KB Output is correct
12 Correct 191 ms 15608 KB Output is correct
13 Correct 113 ms 13048 KB Output is correct
14 Correct 114 ms 12792 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 1 ms 640 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 1 ms 640 KB Output is correct
25 Correct 89 ms 3064 KB Output is correct
26 Correct 2 ms 640 KB Output is correct
27 Correct 938 ms 2816 KB Output is correct
28 Correct 2741 ms 103292 KB Output is correct
29 Correct 3045 ms 86592 KB Output is correct
30 Correct 3086 ms 86584 KB Output is correct
31 Correct 2840 ms 105340 KB Output is correct
32 Correct 1 ms 512 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 2728 KB Output is correct
2 Correct 196 ms 2808 KB Output is correct
3 Correct 259 ms 2688 KB Output is correct
4 Correct 252 ms 2808 KB Output is correct
5 Correct 258 ms 2808 KB Output is correct
6 Correct 117 ms 21496 KB Output is correct
7 Correct 120 ms 21624 KB Output is correct
8 Correct 117 ms 21564 KB Output is correct
9 Correct 156 ms 22904 KB Output is correct
10 Correct 107 ms 12792 KB Output is correct
11 Correct 113 ms 12792 KB Output is correct
12 Correct 204 ms 15736 KB Output is correct
13 Correct 123 ms 12792 KB Output is correct
14 Correct 117 ms 12752 KB Output is correct
15 Correct 5362 ms 181544 KB Output is correct
16 Correct 12127 ms 192164 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 640 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 1 ms 640 KB Output is correct
25 Correct 1 ms 768 KB Output is correct
26 Correct 1 ms 640 KB Output is correct
27 Correct 86 ms 3064 KB Output is correct
28 Correct 1 ms 640 KB Output is correct
29 Correct 993 ms 2808 KB Output is correct
30 Correct 2727 ms 104776 KB Output is correct
31 Correct 10331 ms 189572 KB Output is correct
32 Correct 10944 ms 189436 KB Output is correct
33 Correct 3108 ms 86472 KB Output is correct
34 Correct 10921 ms 156520 KB Output is correct
35 Correct 2936 ms 86392 KB Output is correct
36 Correct 10599 ms 156408 KB Output is correct
37 Correct 2799 ms 106232 KB Output is correct
38 Correct 10627 ms 190104 KB Output is correct
39 Correct 1 ms 512 KB Output is correct
40 Correct 11056 ms 156932 KB Output is correct