Submission #276127

#	Time	Username	Problem	Language	Result	Execution time	Memory
276127		MKopchev	Wombats (IOI13_wombats)	C++14	76 / 100	20033 ms	106248 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24