oj.uz

Submission #276127

# Submission time Handle Problem Language Result Execution time Memory
276127 2020-08-20T11:00:18 Z MKopchev Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 106248 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;
        */
    }
}
int opt[cmax][cmax];

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 58 ms 12792 KB Output is correct
2 Correct 60 ms 12792 KB Output is correct
3 Correct 141 ms 14968 KB Output is correct
4 Correct 69 ms 12792 KB Output is correct
5 Correct 59 ms 12792 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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 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 89 ms 2296 KB Output is correct
12 Correct 1 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1730 ms 2732 KB Output is correct
2 Correct 1732 ms 2808 KB Output is correct
3 Correct 1788 ms 2680 KB Output is correct
4 Correct 1850 ms 2732 KB Output is correct
5 Correct 1835 ms 2808 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 8963 ms 2732 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 69 ms 21592 KB Output is correct
2 Correct 70 ms 21496 KB Output is correct
3 Correct 67 ms 21624 KB Output is correct
4 Correct 108 ms 22776 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 2884 KB Output is correct
2 Correct 1706 ms 2684 KB Output is correct
3 Correct 1867 ms 2736 KB Output is correct
4 Correct 1935 ms 2740 KB Output is correct
5 Correct 1736 ms 2724 KB Output is correct
6 Correct 64 ms 21496 KB Output is correct
7 Correct 64 ms 21604 KB Output is correct
8 Correct 65 ms 21496 KB Output is correct
9 Correct 106 ms 22776 KB Output is correct
10 Correct 59 ms 12928 KB Output is correct
11 Correct 79 ms 12792 KB Output is correct
12 Correct 145 ms 14840 KB Output is correct
13 Correct 70 ms 12792 KB Output is correct
14 Correct 60 ms 12920 KB Output is correct
15 Correct 0 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 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 1 ms 640 KB Output is correct
23 Correct 1 ms 640 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 96 ms 2284 KB Output is correct
26 Correct 1 ms 640 KB Output is correct
27 Correct 8402 ms 2724 KB Output is correct
28 Correct 17463 ms 101776 KB Output is correct
29 Correct 16561 ms 86392 KB Output is correct
30 Correct 15697 ms 86416 KB Output is correct
31 Correct 18180 ms 106248 KB Output is correct
32 Correct 1 ms 384 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 2776 KB Output is correct
2 Correct 1946 ms 2680 KB Output is correct
3 Correct 2049 ms 2736 KB Output is correct
4 Correct 1934 ms 2740 KB Output is correct
5 Correct 1873 ms 2724 KB Output is correct
6 Correct 70 ms 21496 KB Output is correct
7 Correct 72 ms 21576 KB Output is correct
8 Correct 76 ms 21596 KB Output is correct
9 Correct 122 ms 22904 KB Output is correct
10 Correct 64 ms 12792 KB Output is correct
11 Correct 68 ms 12844 KB Output is correct
12 Correct 166 ms 15248 KB Output is correct
13 Correct 61 ms 12832 KB Output is correct
14 Correct 66 ms 12792 KB Output is correct
15 Execution timed out 20033 ms 66772 KB Time limit exceeded
16 Halted 0 ms 0 KB -