oj.uz

Submission #3334

# Submission time Handle Problem Language Result Execution time Memory
3334 2013-08-30T12:27:55 Z The_KMJ_God 일도양단! (kriii1_1) C++
1 / 1
 0 ms 2700 KB 
// 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2700 KB Output is correct
2 Correct 0 ms 2700 KB Output is correct
3 Correct 0 ms 2700 KB Output is correct
4 Correct 0 ms 2700 KB Output is correct
5 Correct 0 ms 2700 KB Output is correct
6 Correct 0 ms 2700 KB Output is correct
7 Correct 0 ms 2700 KB Output is correct
8 Correct 0 ms 2700 KB Output is correct
9 Correct 0 ms 2700 KB Output is correct
10 Correct 0 ms 2700 KB Output is correct
11 Correct 0 ms 2700 KB Output is correct
12 Correct 0 ms 2700 KB Output is correct
13 Correct 0 ms 2700 KB Output is correct
14 Correct 0 ms 2700 KB Output is correct
15 Correct 0 ms 2700 KB Output is correct
16 Correct 0 ms 2700 KB Output is correct
17 Correct 0 ms 2700 KB Output is correct
18 Correct 0 ms 2700 KB Output is correct
19 Correct 0 ms 2700 KB Output is correct
20 Correct 0 ms 2700 KB Output is correct
21 Correct 0 ms 2700 KB Output is correct
22 Correct 0 ms 2700 KB Output is correct
23 Correct 0 ms 2700 KB Output is correct
24 Correct 0 ms 2700 KB Output is correct
25 Correct 0 ms 2700 KB Output is correct
26 Correct 0 ms 2700 KB Output is correct
27 Correct 0 ms 2700 KB Output is correct
28 Correct 0 ms 2700 KB Output is correct
29 Correct 0 ms 2700 KB Output is correct
30 Correct 0 ms 2700 KB Output is correct
31 Correct 0 ms 2700 KB Output is correct
32 Correct 0 ms 2700 KB Output is correct
33 Correct 0 ms 2700 KB Output is correct
34 Correct 0 ms 2700 KB Output is correct
35 Correct 0 ms 2700 KB Output is correct
36 Correct 0 ms 2700 KB Output is correct
37 Correct 0 ms 2700 KB Output is correct
38 Correct 0 ms 2700 KB Output is correct
39 Correct 0 ms 2700 KB Output is correct
40 Correct 0 ms 2700 KB Output is correct
41 Correct 0 ms 2700 KB Output is correct
42 Correct 0 ms 2700 KB Output is correct
43 Correct 0 ms 2700 KB Output is correct
44 Correct 0 ms 2700 KB Output is correct
45 Correct 0 ms 2700 KB Output is correct
46 Correct 0 ms 2700 KB Output is correct
47 Correct 0 ms 2700 KB Output is correct
48 Correct 0 ms 2700 KB Output is correct
49 Correct 0 ms 2700 KB Output is correct
50 Correct 0 ms 2700 KB Output is correct
51 Correct 0 ms 2700 KB Output is correct
52 Correct 0 ms 2700 KB Output is correct
53 Correct 0 ms 2700 KB Output is correct
54 Correct 0 ms 2700 KB Output is correct
55 Correct 0 ms 2700 KB Output is correct
56 Correct 0 ms 2700 KB Output is correct
57 Correct 0 ms 2700 KB Output is correct
58 Correct 0 ms 2700 KB Output is correct
59 Correct 0 ms 2700 KB Output is correct
60 Correct 0 ms 2700 KB Output is correct
61 Correct 0 ms 2700 KB Output is correct
62 Correct 0 ms 2700 KB Output is correct
63 Correct 0 ms 2700 KB Output is correct
64 Correct 0 ms 2700 KB Output is correct
65 Correct 0 ms 2700 KB Output is correct
66 Correct 0 ms 2700 KB Output is correct
67 Correct 0 ms 2700 KB Output is correct
68 Correct 0 ms 2700 KB Output is correct
69 Correct 0 ms 2700 KB Output is correct
70 Correct 0 ms 2700 KB Output is correct
71 Correct 0 ms 2700 KB Output is correct
72 Correct 0 ms 2700 KB Output is correct
73 Correct 0 ms 2700 KB Output is correct
74 Correct 0 ms 2700 KB Output is correct
75 Correct 0 ms 2700 KB Output is correct
76 Correct 0 ms 2700 KB Output is correct
77 Correct 0 ms 2700 KB Output is correct
78 Correct 0 ms 2700 KB Output is correct
79 Correct 0 ms 2700 KB Output is correct
80 Correct 0 ms 2700 KB Output is correct
81 Correct 0 ms 2700 KB Output is correct
82 Correct 0 ms 2700 KB Output is correct
83 Correct 0 ms 2700 KB Output is correct
84 Correct 0 ms 2700 KB Output is correct
85 Correct 0 ms 2700 KB Output is correct
86 Correct 0 ms 2700 KB Output is correct
87 Correct 0 ms 2700 KB Output is correct
88 Correct 0 ms 2700 KB Output is correct
89 Correct 0 ms 2700 KB Output is correct
90 Correct 0 ms 2700 KB Output is correct
91 Correct 0 ms 2700 KB Output is correct
92 Correct 0 ms 2700 KB Output is correct
93 Correct 0 ms 2700 KB Output is correct
94 Correct 0 ms 2700 KB Output is correct
95 Correct 0 ms 2700 KB Output is correct
96 Correct 0 ms 2700 KB Output is correct
97 Correct 0 ms 2700 KB Output is correct
98 Correct 0 ms 2700 KB Output is correct
99 Correct 0 ms 2700 KB Output is correct
100 Correct 0 ms 2700 KB Output is correct