Submission #3334

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

1

// Problem 1. 일도양단!

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;

bool Raisin[8][8][8];
int R,C,H,n,r,c,h;
int dp[8][8][8][8][8][8];
int sum[8][8][8];

int FUNCTION(int a, int b, int c, int d, int e, int f, int cnt) {
	if ( cnt==1 ) return (d-a+1)*(e-b+1)*(f-c+1);
	if ( dp[a][b][c][d][e][f]!=-1 ) return dp[a][b][c][d][e][f];
	int i,j,maximum=-1,kkk;
	for ( i=a; i<d; i++ ) {
		for ( j=c,kkk=0; j<=f; j++ ) {
			kkk+=(sum[i][e][j]-sum[a-1][e][j]-sum[i][b-1][j]+sum[a-1][b-1][j]);
		}
		if ( kkk!=0 && kkk!=cnt ) maximum = max ( maximum , min( FUNCTION(a,b,c,i,e,f,kkk) , FUNCTION(i+1,b,c,d,e,f,cnt-kkk) ) );
	}
	for ( i=b; i<e; i++ ) {
		for ( j=c,kkk=0; j<=f; j++ ) {
			kkk+=(sum[d][i][j]-sum[a-1][i][j]-sum[d][b-1][j]+sum[a-1][b-1][j]);
		}
		if ( kkk!=0 && kkk!=cnt ) 
		maximum = max ( maximum , min( FUNCTION(a,b,c,d,i,f,kkk) , FUNCTION(a,i+1,c,d,e,f,cnt-kkk) ) );
	}
	for ( i=c; i<f; i++ ) {
		for ( j=c,kkk=0; j<=i; j++ ) {
			kkk+=(sum[d][e][j]-sum[d][b-1][j]-sum[a-1][e][j]+sum[a-1][b-1][j]);
		}
		maximum = max ( maximum , min( FUNCTION(a,b,c,d,e,i,kkk) , FUNCTION(a,b,i+1,d,e,f,cnt-kkk) ) );
	}
	return dp[a][b][c][d][e][f]=maximum;
}

int main() {
	int i,j,k;
	memset(dp,-1,sizeof(dp));
	scanf("%d %d %d %d",&R,&C,&H,&n);
	for ( i=0; i<n; i++ )
	{
		scanf("%d %d %d",&r,&c,&h);
		Raisin[r][c][h]=true;
	}
	for ( i=1; i<=H; i++ ) {
		for ( j=1; j<=R; j++ ) {
			for ( k=1; k<=C; k++ ) {
				if ( Raisin[j][k][i] ) sum[j][k][i]=sum[j-1][k][i]+sum[j][k-1][i]-sum[j-1][k-1][i]+1;
				else sum[j][k][i]=sum[j-1][k][i]+sum[j][k-1][i]-sum[j-1][k-1][i];
			}
		}
	}
	printf("%d\n",FUNCTION(1,1,1,R,C,H,n));
	return 0;	
}

• Subtask 1: 1 / 1