Submission #337906

#	Time	Username	Problem	Language	Result	Execution time	Memory
337906		boykut	Bomb (IZhO17_bomb)	C++14	24 / 100	470 ms	9096 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2501;

//int dp[MAXN][MAXN];
char a[MAXN][MAXN];
//int sum[MAXN][MAXN];

signed main() {
   int n, m;
   cin >> n >> m;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         cin >> a[i][j];
         //sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+int(a[i][j] == '1');
      }
   }
   //for (int i = 1; i <= n; i++) {
   //   for (int j = 1; j <= n; j++) {
   //     for (int a = 1; a <= i; a++) {
   //         for (int b = 1; b <= j; b++) {
   //            if (get(a, b, i, j))
   //               dp[i - a + 1][j - b + 1] = 1;
   //         }
   //      }
   //   }
   //}
   int mnj = INT_MAX, mni = INT_MAX;
   for (int i = 1; i <= n; i++) {
      for (int l = 1; l <= m;) {
         int r = l, cnt = 0;
         while (r <= m && a[i][r] == '1') r++, cnt++;
         l = r + 1;
         if (cnt)
            mnj = min(mnj, cnt);
      }
   }
   for (int j = 1; j <= m; j++) {
      for (int l = 1; l <= n;) {
         int r = l, cnt = 0;
         while (r <= n && a[r][j] == '1') r++, cnt++;
         l = r + 1;
         if (cnt)
            mni = min(mni, cnt);
      }
   }
   if (mni == INT_MAX) cout << 0;
   else cout << mni * mnj << '\n';
   return 0;
}

• Subtask 1: 24 / 100