Submission #1988565


Source Code Expand

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int *array;
	int N;
}stack;

stack *make_stack(int maxN){
	stack *s = (stack *)malloc(sizeof(stack));
	s->array = (int *)malloc(sizeof(int) * maxN);
	s->N = 0;
	return s;
}

int element_num_stack(stack *s){
	return s->N;
}

void add_data_stack(int val, stack *s){
	s->array[s->N] = val;
	s->N++;
}

int take_data_stack(stack *s){
	if(s->N == 0){
		printf("no data in the stack\n");
	}
	s->N--;
	return s->array[s->N];
}

int look_data_stack(stack *s){
	if(s->N == 0){
		printf("no data in the stack\n");
	}
	else{
		return s->array[s->N - 1];
	}
}

void flush_stack(stack *s){
	s->N = 0;
}

long long max(long long a, long long b){
	return a >= b ? a : b;
}

//Aの各要素は0か1
//1だけから成る長方形の面積の最大値を返す
int largest_rectangle(int H, int W, int **A){
	int i, j, garbage, ans = 0;
	int **T = (int **)malloc(sizeof(int *) * H);
	int *L = (int *)malloc(sizeof(int) * W);
	int *R = (int *)malloc(sizeof(int) * W);
	stack *sL = make_stack(W);
	stack *sR = make_stack(W);
	for(i = 0; i < H; i++){
		T[i] = (int *)malloc(sizeof(int) * W);
		for(j = 0; j < W; j++){
			if(i == 0){
				T[i][j] = A[i][j];
			}
			else{
				T[i][j] = (T[i - 1][j] + 1) * A[i][j];
			}
		}

		for(j = 0; j < W; j++){
			while(1){
				if(element_num_stack(sL) == 0){
					L[j] = 0;
					break;
				}
				else if(T[i][j] > T[i][look_data_stack(sL)]){
					L[j] = look_data_stack(sL) + 1;
					break;
				}
				garbage = take_data_stack(sL);
			}
			add_data_stack(j, sL);
		}
		flush_stack(sL);

		for(j = W - 1; j >= 0; j--){
			while(1){
				if(element_num_stack(sR) == 0){
					R[j] = W - 1;
					break;
				}
				else if(T[i][j] > T[i][look_data_stack(sR)]){
					R[j] = look_data_stack(sR) - 1;
					break;
				}
				garbage = take_data_stack(sR);
			}
			add_data_stack(j, sR);
		}
		flush_stack(sR);

		for(j = 0; j < W; j++){
			ans = max(ans, ((T[i][j] + 1) / 2) * ((R[j] - L[j] + 2) / 2));
		}
	}
	return ans;
}

int main(){
	int H, W, i, j, count;
	scanf("%d%d", &H, &W);
	char **S = (char **)malloc(sizeof(char *) * H);
	for(i = 0; i < H; i++){
		S[i] = (char *)malloc(sizeof(char) * (W + 1));
		scanf("%s", S[i]);
	}
	int **A = (int **)malloc(sizeof(int *) * (2 * H - 1));
	for(i = 0; i < 2 * H - 1; i++){
		A[i] = (int *)malloc(sizeof(int) * (2 * W - 1));
		for(j = 0; j < 2 * W - 1; j++){
			A[i][j] = 1;
		}
	}
	for(i = 1; i < H; i++){
		for(j = 1; j < W; j++){
			count = 0;
			if(S[i][j] == '#'){
				count++;
			}
			if(S[i - 1][j] == '#'){
				count++;
			}
			if(S[i][j - 1] == '#'){
				count++;
			}
			if(S[i - 1][j - 1] == '#'){
				count++;
			}
			if(count == 1 || count == 3){
				A[2 * i - 1][2 * j - 1] = 0;
			}
		}
	}
	printf("%d\n", largest_rectangle(2 * H - 1, 2 * W - 1, A));
	return 0;
}

Submission Info

Submission Time
Task F - Flip and Rectangles
User abc050
Language C (GCC 5.4.1)
Score 700
Code Size 2935 Byte
Status AC
Exec Time 476 ms
Memory 129280 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:111:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
  ^
./Main.c:115:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S[i]);
   ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 40
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt AC 1 ms 512 KB
10.txt AC 461 ms 129280 KB
11.txt AC 156 ms 67456 KB
12.txt AC 299 ms 128256 KB
13.txt AC 310 ms 129152 KB
14.txt AC 327 ms 128384 KB
15.txt AC 328 ms 129280 KB
16.txt AC 328 ms 129280 KB
17.txt AC 326 ms 129280 KB
18.txt AC 470 ms 128256 KB
19.txt AC 387 ms 129152 KB
2.txt AC 1 ms 256 KB
20.txt AC 402 ms 128384 KB
21.txt AC 401 ms 129280 KB
22.txt AC 399 ms 129280 KB
23.txt AC 408 ms 129280 KB
24.txt AC 269 ms 129280 KB
25.txt AC 269 ms 129280 KB
26.txt AC 471 ms 129280 KB
27.txt AC 445 ms 129280 KB
28.txt AC 397 ms 129280 KB
29.txt AC 305 ms 129280 KB
3.txt AC 421 ms 129152 KB
30.txt AC 319 ms 129280 KB
31.txt AC 322 ms 129280 KB
32.txt AC 328 ms 129280 KB
33.txt AC 334 ms 129280 KB
34.txt AC 331 ms 129280 KB
4.txt AC 419 ms 129280 KB
5.txt AC 1 ms 512 KB
6.txt AC 1 ms 256 KB
7.txt AC 476 ms 129280 KB
8.txt AC 475 ms 129280 KB
9.txt AC 458 ms 129280 KB
sample1.txt AC 1 ms 128 KB
sample2.txt AC 1 ms 128 KB
sample3.txt AC 1 ms 128 KB