Submission #586724

#	Time	Username	Problem	Language	Result	Execution time	Memory
586724		yutabi	Wombats (IOI13_wombats)	C++14	39 / 100	20027 ms	262144 KiB

wombats

#include "wombats.h"

#include <bits/stdc++.h>
using namespace std;


typedef pair <int,int> ii;


vector <vector <vector <int> > > DP;

int r;
int c;

vector <vector <int> > horizontal;
vector <vector <int> > vertical;

void recalc()
{
    for(int i=0;i<c;i++)
    {
        for(int j=0;j<r;j++)
        {
            if(j==0)
            {
                for(int k=0;k<c;k++)
                {
                    DP[i][0][k]=1000000007;
                }

                DP[i][0][i]=0;
            }

            else
            {
                for(int k=0;k<c;k++)
                {
                    DP[i][j][k]=DP[i][j-1][k]+vertical[j-1][k];
                }
            }

            vector <bool> v(c,0);
            priority_queue <ii> pq;

            for(int k=0;k<c;k++)
            {
                pq.push(ii(-DP[i][j][k],k));
            }

            while(pq.size())
            {
                int ptr=pq.top().second;

                pq.pop();

                if(v[ptr])
                {
                    continue;
                }

                v[ptr]=1;

                if(ptr<c-1)
                {
                    if(DP[i][j][ptr]+horizontal[j][ptr]<DP[i][j][ptr+1])
                    {
                        DP[i][j][ptr+1]=DP[i][j][ptr]+horizontal[j][ptr];

                        pq.push(ii(-DP[i][j][ptr+1],ptr+1));
                    }
                }

                if(ptr>0)
                {
                    if(DP[i][j][ptr]+horizontal[j][ptr-1]<DP[i][j][ptr-1])
                    {
                        DP[i][j][ptr-1]=DP[i][j][ptr]+horizontal[j][ptr-1];

                        pq.push(ii(-DP[i][j][ptr-1],ptr-1));
                    }
                }
            }
        }
    }

    /*for(int i=0;i<c;i++)
    {
        for(int j=0;j<r;j++)
        {
            for(int k=0;k<c;k++)
            {
                printf("%d ",DP[i][j][k]);
            }

            printf("\n");
        }

        printf("\n");
    }*/
}


void init(int R, int C, int H[5000][200], int V[5000][200])
{
    DP=vector <vector <vector <int> > > (C,vector <vector <int> > (R,vector <int> (C)));

    r=R;
    c=C;

    horizontal=vector <vector <int> > (R,vector <int> (C-1));
    vertical=vector <vector <int> > (R-1,vector <int> (C));

    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            if(i+1!=r)
            {
                vertical[i][j]=V[i][j];
            }

            if(j+1!=c)
            {
                horizontal[i][j]=H[i][j];
            }
        }
    }

    recalc();
}

void changeH(int P, int Q, int W)
{
    horizontal[P][Q]=W;

    recalc();
}

void changeV(int P, int Q, int W)
{
    vertical[P][Q]=W;

    recalc();
}

int escape(int V1, int V2)
{
    return DP[V1][r-1][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: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24