제출 #1230773

#제출 시각아이디문제언어결과실행 시간메모리
1230773MatthewwwwBomb (IZhO17_bomb)C++17
24 / 100
150 ms49476 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> grid;
	if (n < m) {
		grid.resize(n, vector<int>(m));	
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			grid[i][j] = c == '1';
		}
	} else {
		grid.resize(m, vector<int>(n));
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			grid[j][i] = c == '1';
		}
		swap(n, m);
	}
	// lets try proof by ac!
	int mx = n, my = m;
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> ran;
		for (int j = 0; j < m; j++) {
			if (!grid[i][j]) continue;
			if (!ran.size() || ran.back().s != j)
				ran.push_back({j, j+1});
			else
				ran.back().s++;
		}
		for (auto j: ran) my = min(my, j.s-j.f);
	}
	for (int i = 0; i < m; i++) {
		vector<pair<int, int>> ran;
		for (int j = 0; j < n; j++) {
			if (!grid[j][i]) continue;
			if (!ran.size() || ran.back().s != j)
				ran.push_back({j, j+1});
			else
				ran.back().s++;
		}
		for (auto j: ran) mx = min(mx, j.s-j.f);
	}
	cout << mx*my << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...