Submission #38394

#	Time	Username	Problem	Language	Result	Execution time	Memory
38394		mirbek01	Bomb (IZhO17_bomb)	C++14	41 / 100	1000 ms	32656 KiB

bomb

# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 2505;

typedef long long ll;

int n, m, a = inf, b = inf, pref[N][N];
char ch[N][N];

int get(int l, int r, int l2, int r2){
      return pref[l2][r2] - pref[l2][r - 1] - pref[l - 1][r2] + pref[l - 1][r - 1];
}

int main(){
      scanf("%d %d", &n, &m);
      int cnt = 0;
      for(int i = 1; i <= n; i ++){
            scanf("\n");
            for(int j = 1; j <= m; j ++){
                  scanf("%c", &ch[i][j]);
                  if(ch[i][j] == '1') cnt ++;
            }
      }

      if(!cnt){
            printf("0");
            return 0;
      }

      for(int i = 1; i <= n; i ++){
            int cur = 0;
            for(int j = 1; j <= m; j ++){
                  if(ch[i][j] == '1') cur ++;
                  else{
                        if(cur) a = min(a, cur);
                        cur = 0;
                  }
            }
            if(cur) a = min(a, cur);
      }

      for(int i = 1; i <= m; i ++){
            int cur = 0;
            for(int j = 1; j <= n; j ++){
                  if(ch[j][i] == '1') cur ++;
                  else {
                        if(cur) b = min(b, cur);
                        cur = 0;
                  }
            }
            if(cur) b = min(b, cur);
      }
      if(n > 100 || m > 100){
            printf("%d", a * b);
      } else {
            for(int i = 1; i <= n; i ++){
                  for(int j = 1; j <= m; j ++){
                        if(ch[i][j] == '1') pref[i][j] ++;
                        pref[i][j] += pref[i][j - 1];
                  }
            }
            for(int i = 1; i <= n; i ++)
                  for(int j = 1; j <= m; j ++)
                        pref[i][j] += pref[i - 1][j];
            int ans = 0;
            for(int x = 1; x <= n; x ++){
                  for(int y = 1; y <= m; y ++){
                        if(x * y <= ans) continue;
                        int used[101][101];
                        for(int i = 1; i <= n; i ++)
                              for(int j = 1; j <= m; j ++)
                                    used[i][j] = 0;
                        for(int i = 1; i <= n - x + 1; i ++){
                              for(int j = 1; j <= m - y + 1; j ++){
                                    int i1 = i + x - 1, j1 = j + y - 1;
                                    if(get(i, j, i1, j1) == x * y){
                                          for(int xx = i; xx <= i1; xx ++){
                                                for(int yy = j; yy <= j1; yy ++){
                                                      used[xx][yy] = 1;
                                                }
                                          }
                                    }
                              }
                        }
                        int fl = true;
                        for(int i = 1; i <= n; i ++){
                              for(int j = 1; j <= m; j ++){
                                    if(ch[i][j] == '1' && !used[i][j]) fl = false;
                              }
                        }
                        if(fl) ans = max(ans, x * y);
                  }
            }
            printf("%d", ans);
      }
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:25:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
                             ^
bomb.cpp:28:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("\n");
                        ^
bomb.cpp:30:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                   scanf("%c", &ch[i][j]);
                                         ^

• Subtask 1: 41 / 100