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
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
AC × 5
AC × 25
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