Submission #4023773
Source Code Expand
#include <stdio.h>
#define MAX_COL (101) /* 最大列数 */
#define MAX_ROW (101) /* 最大行数 */
/* デバッグ用2次元配列表示 */
void print2d(int h, int w, int ary[MAX_COL][MAX_COL]);
void accum(int n, int input[MAX_COL], int output[MAX_COL]); /* 累積和 */
void accum2d(int h, int w, int input[MAX_COL][MAX_COL], int output[MAX_COL][MAX_COL]); /* 2次元累積和 */
int main(){
int sum_ary[MAX_COL][MAX_COL]; /* 左上からの矩形領域の2次元累積和 */
int h,w,c[MAX_COL][MAX_COL]; /* 入力 */
int hs,ws,he,we; /* ループ用一時変数(h,wそれぞれの開始位置/終了位置) */
int max_cell_num; /* 領域数の最大値 */
int cell_num; /* 領域数 */
int sum; /* 濃度の合計 */
/* 入力 */
scanf("%d %d",&h,&w);
for(hs=1;hs<=h;hs++){
for(ws=1;ws<=w;ws++){
scanf("%d",&(c[hs][ws]));
/* 黒はマイナス値で保持する */
if((hs+ws)%2==0){
c[hs][ws]=-c[hs][ws];
}
}
}
/* 後の計算を楽にするため、入力領域の左列と上行に0を番兵として入れておく */
for(hs=0;hs<=h;hs++){
c[hs][0] = 0;
}
for(ws=0;ws<=w;ws++){
c[0][ws] = 0;
}
/* 累積和計算 */
accum2d(h+1,w+1,c,sum_ary);
/* 最大の領域を探索 */
/* 矩形領域のパターン(左上が(hs,ws),右下が(he,we)となる矩形)を全探索 */
/* 黒をマイナス、白をプラスの値としているため、領域の合計が0になれば条件を満たす */
max_cell_num = 0;
for(hs=1;hs<=h;hs++){
for(ws=1;ws<=w;ws++){
for(he=hs;he<=h;he++){
for(we=ws;we<=w;we++){
/* 領域の濃度合計計算 */
sum = sum_ary[he][we] - sum_ary[hs-1][we] - sum_ary[he][ws-1] + sum_ary[hs-1][ws-1];
if(sum == 0){
/* 領域のサイズ計算 */
cell_num = (he-hs+1)*(we-ws+1);
if(max_cell_num < cell_num){
max_cell_num = cell_num;
}
}
}
}
}
}
/* 出力 */
printf("%d\n",max_cell_num);
}
/* 累積和 */
/* 長さ n の配列 input に対し、先頭からの累積和をoutputに入れる */
void accum(int n, int input[MAX_COL], int output[MAX_COL]){
int i;
output[0] = input[0];
for(i=1;i<n;i++){
output[i] = output[i-1] + input[i];
}
}
/* 2次元累積和 */
/* 高さ h、幅 w の2次元配列 inputに対し、左上からの累積和を2次元配列outputに入れる */
void accum2d(int h, int w, int input[MAX_COL][MAX_COL], int output[MAX_COL][MAX_COL]){
int hi,wi;
accum(w,input[0],output[0]);
for(hi=1;hi<h;hi++){
accum(w,input[hi],output[hi]);
for(wi=0;wi<w;wi++){
output[hi][wi] += output[hi-1][wi];
}
}
}
/* デバッグ用2次元配列表示 */
void print2d(int h, int w, int ary[MAX_COL][MAX_COL]){
int hi,wi;
for(hi=0;hi<h;hi++){
for(wi=0;wi<w;wi++){
printf("%d ",ary[hi][wi]);
}
printf("\n");
}
}
Submission Info
Submission Time
2019-01-16 15:00:42+0900
Task
B - チョコレート
User
mayumini
Language
C (GCC 5.4.1)
Score
100
Code Size
3436 Byte
Status
AC
Exec Time
53 ms
Memory
256 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:21:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&h,&w);
^
./Main.c:24:13: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&(c[hs][ws]));
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 100
Status
Set Name
Test Cases
Sample
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt
All
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt
Case Name
Status
Exec Time
Memory
subtask0_sample-01.txt
AC
1 ms
128 KB
subtask0_sample-02.txt
AC
1 ms
128 KB
subtask0_sample-03.txt
AC
1 ms
128 KB
subtask0_sample-04.txt
AC
1 ms
128 KB
subtask0_sample-05.txt
AC
1 ms
128 KB
subtask1_01.txt
AC
1 ms
128 KB
subtask1_02.txt
AC
1 ms
128 KB
subtask1_03.txt
AC
1 ms
128 KB
subtask1_04.txt
AC
1 ms
128 KB
subtask1_05.txt
AC
1 ms
128 KB
subtask1_06.txt
AC
1 ms
128 KB
subtask1_07.txt
AC
1 ms
128 KB
subtask1_08.txt
AC
1 ms
128 KB
subtask1_09.txt
AC
51 ms
256 KB
subtask1_10.txt
AC
9 ms
256 KB
subtask1_11.txt
AC
38 ms
256 KB
subtask1_12.txt
AC
38 ms
256 KB
subtask1_13.txt
AC
38 ms
256 KB
subtask1_14.txt
AC
52 ms
256 KB
subtask1_15.txt
AC
53 ms
256 KB
subtask1_16.txt
AC
37 ms
256 KB
subtask1_17.txt
AC
41 ms
256 KB
subtask1_18.txt
AC
1 ms
128 KB
subtask1_19.txt
AC
1 ms
256 KB
subtask1_20.txt
AC
43 ms
256 KB