Submission #38944

#	Time	Username	Problem	Language	Result	Execution time	Memory
38944		touristk2000	Bomb (IZhO17_bomb)	C++14	0 / 100	0 ms	49992 KiB

bomb

#include <stdio.h>
const int maxn = 2501;
int dp[maxn][maxn];
int a[maxn][maxn];
int p[maxn];
int t;///;[maxn];
int n, m, res = 1;
bool check(int i, int j){
            for(int c = 1; c <= m; c ++) p[c] = n + 1;
            bool f = true;
            for(int I = n; I >= 1 && f; I --){
                int q = m + 1;
                for(int J = m; J >= 1 && f; J --){
                    if(I>=i&&J>=j){
                    if(dp[I][J] - dp[I-i][J] - dp[I][J-j] + dp[I-i][J-j] == i * j){
                        q = J - j;
                    }}
                    if(J > q) p[J] = I-i;
                    if(a[I][J] && p[J] >= I) f = false;
                }
            }
            return f;
}
int main(){
    freopen("bomb.in", "r", stdin);
    freopen("bomb.out", "w", stdout);
    char c;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        c = getchar();
        for(int j = 1; j <= m; j ++){
            a[i][j] = dp[i][j] = getchar() - '0';
            dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
        }
    }
    t = m;
    ///for(int i = 1; i <= m; i ++)t[i] = m;
    for(int i = 1; i <= n; i ++){
        int L = 1, R = t, M;
        while(L <= R){
            M = (L + R) >> 1;
            if(check(i, M)){
                if(i * M > res) res = i * M;
                L = M + 1;
            }else
            R = M - 1;
        }
        t = R;
    }
    printf("%d", res);
    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:27:10: warning: variable 'c' set but not used [-Wunused-but-set-variable]
     char c;
          ^
bomb.cpp:25:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("bomb.in", "r", stdin);
                                   ^
bomb.cpp:26:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("bomb.out", "w", stdout);
                                     ^
bomb.cpp:28:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^

• Subtask 1: 0 / 100