Submission #429250

#	Time	Username	Problem	Language	Result	Execution time	Memory
429250		rumen_m	Wombats (IOI13_wombats)	C++17	100 / 100	11990 ms	191860 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];
 
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 (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: 24 / 24