Submission #8349

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

1

#include <stdio.h>
  
int R,C,H,N,G[8][8][8];
int D[8][8][8][8][8][8];
  
int min(int a, int b){return a < b ? a : b;}
int max(int a, int b){return a > b ? a : b;}
int sum(int x1, int x2, int y1, int y2, int z1, int z2)
{
    return G[x2][y2][z2] - G[x1-1][y2][z2] - G[x2][y1-1][z2] - G[x2][y2][z1-1] + G[x1-1][y1-1][z2] + G[x1-1][y2][z1-1] + G[x2][y1-1][z1-1] - G[x1-1][y1-1][z1-1];
}
  
int main()
{
    int x,y,z,i;
  
    scanf ("%d %d %d %d",&R,&C,&H,&N);
    for (i=0;i<N;i++){
        scanf ("%d %d %d",&x,&y,&z);
        G[x][y][z]++;
    }
  
    for (x=1;x<=R;x++) for (y=1;y<=C;y++) for (z=1;z<=H;z++){
        G[x][y][z] += G[x-1][y][z] + G[x][y-1][z] + G[x][y][z-1];
        G[x][y][z] -= G[x-1][y-1][z] + G[x-1][y][z-1] + G[x][y-1][z-1];
        G[x][y][z] += G[x-1][y-1][z-1];
    }
  
    int r,r1,r2,c,c1,c2,h,h1,h2;
  
    for (r=1;r<=R;r++) for (r1=1,r2=r;r2<=R;r1++,r2++){
        for (c=1;c<=C;c++) for (c1=1,c2=c;c2<=C;c1++,c2++){
            for (h=1;h<=H;h++) for (h1=1,h2=h;h2<=H;h1++,h2++){
                int s = sum(r1,r2,c1,c2,h1,h2);
                int v = r * c * h;
                  
                int &d = D[r1][r2][c1][c2][h1][h2];
                if (s == 0) d = -1;
                else if (s == 1) d = v;
                else{
                    for (i=r1;i<r2;i++) d = max(d,min(D[r1][i][c1][c2][h1][h2],D[i+1][r2][c1][c2][h1][h2]));
                    for (i=c1;i<c2;i++) d = max(d,min(D[r1][r2][c1][i][h1][h2],D[r1][r2][i+1][c2][h1][h2]));
                    for (i=h1;i<h2;i++) d = max(d,min(D[r1][r2][c1][c2][h1][i],D[r1][r2][c1][c2][i+1][h2]));
                }
            }
        }
    }
  
    printf ("%d\n",D[1][R][1][C][1][H]);
  
    return 0;
}

• Subtask 1: 1 / 1