Submission #5364

#	Time	Username	Problem	Language	Result	Execution time	Memory
5364		baneling100	일도양단! (kriii1_1)	C++98	0 / 1	0 ms	3136 KiB

1

#include <stdio.h>
#define inf 1000000000

int R, C, H, N, d[8][8][8][8][8][8], grape[8][8][8][8][8][8];

void input(void)
{
    int i, r, c, h;

    scanf("%d %d %d %d",&R,&C,&H,&N);
    for(i=1 ; i<=N ; i++)
    {
        scanf("%d %d %d",&r,&c,&h);
        grape[r][r][c][c][h][h]=1;
    }
}

void process(void)
{
    int i, j, k, l, r1, r2, c1, c2, h1, h2;

    for(i=1 ; i<=R ; i++)
        for(j=1 ; j<=C ; j++)
            for(k=1 ; k<=H ; k++)
                for(r1=1 ; r1<=R-i+1 ; r1++)
                {
                    r2=r1+i-1;
                    for(c1=1 ; c1<=C-j+1 ; c1++)
                    {
                        c2=c1+j-1;
                        for(h1=1 ; h1<=H-k+1 ; h1++)
                        {
                            h2=h1+k-1;
                            if(i>=2)
                                grape[r1][r2][c1][c2][h1][h2]=grape[r1][r2-1][c1][c2][h1][h2]+grape[r2][r2][c1][c2][h1][h2];
                            else if(j>=2)
                                grape[r1][r2][c1][c2][h1][h2]=grape[r1][r2][c1][c2-1][h1][h2]+grape[r1][r2][c2][c2][h1][h2];
                            else if(k>=2)
                                grape[r1][r2][c1][c2][h1][h2]=grape[r1][r2][c1][c2][h1][h2-1]+grape[r1][r2][c1][c2][h2][h2];
                            for(l=r1 ; l<=r2-1 ; l++)
                            {
                                if(grape[r1][l][c1][c2][h1][h2] && grape[l+1][r2][c1][c2][h1][h2])
                                {
                                    if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2]+1)
                                        d[r1][r2][c1][c2][h1][h2]=d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2]+1;
                                }
                                else
                                    if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2])
                                        d[r1][r2][c1][c2][h1][h2]=d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2];
                            }
                            for(l=c1 ; l<=c2-1 ; l++)
                            {
                                if(grape[r1][r2][c1][l][h1][h2] && grape[r1][r2][l+1][c2][h1][h2])
                                {
                                    if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2]+1)
                                        d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2]+1;
                                }
                                else
                                    if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2])
                                        d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2];
                            }
                            for(l=h1 ; l<=h2-1 ; l++)
                            {
                                if(grape[r1][r2][c1][c2][h1][l] && grape[r1][r2][c1][c2][l+1][h2])
                                {
                                    if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2]+1)
                                        d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2]+1;
                                }
                                else
                                    if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2])
                                        d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2];
                            }
                        }
                    }
                }
}

void output(void)
{
    printf("%d",d[1][R][1][C][1][H]);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 0 / 1