Submission #833274

#	Time	Username	Problem	Language	Result	Execution time	Memory
833274		vjudge1	Bomb (IZhO17_bomb)	C++17	24 / 100	171 ms	24920 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

const int MX = 2505;
int N, M;
int A[MX][MX];

int solve(vector<int> v) {
      int mn = 1e9;

      vector<int> lf(v.size()), rg(v.size());

      for(int i = 0; i < v.size(); i++) {
            if(v[i] == 1) {
                  if(i - 1 < 0 || v[i - 1] == 0) lf[i] = i;
                  else lf[i] = lf[i - 1];
            }
      }

      for(int i = v.size() - 1; i >= 0; i--) {
            if(v[i] == 1) {
                  if(i + 1 == v.size() || v[i + 1] == 0) rg[i] = i;
                  else rg[i] = rg[i + 1];
            }
      }

      for(int i = 0; i < v.size(); i++) {
            if(v[i] == 1) {
                  mn = min(mn, rg[i] - lf[i] + 1);
            }
      }

      return mn;
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> M;
      for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                  char c;
                  cin >> c;
                  if(c == '1') A[i][j] = 1;
            }
      }

      int minRow = 1e9, minCol = 1e9;
      for(int i = 0; i < N; i++) {
            vector<int> v;
            for(int j = 0; j < M; j++) v.push_back(A[i][j]);
            minRow = min(minRow, solve(v));
      }

      for(int j = 0; j < M; j++) {
            vector<int> v;
            for(int i = 0; i < N; i++) v.push_back(A[i][j]);
            minCol = min(minCol, solve(v));
      }

      cout << minRow * minCol << '\n';
}

Compilation message (stderr)

bomb.cpp: In function 'int solve(std::vector<int>)':
bomb.cpp:13:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |       for(int i = 0; i < v.size(); i++) {
      |                      ~~^~~~~~~~~~
bomb.cpp:22:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |                   if(i + 1 == v.size() || v[i + 1] == 0) rg[i] = i;
      |                      ~~~~~~^~~~~~~~~~~
bomb.cpp:27:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |       for(int i = 0; i < v.size(); i++) {
      |                      ~~^~~~~~~~~~

• Subtask 1: 24 / 100