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 |
|
|
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 |