Submission #93280

#	Time	Username	Problem	Language	Result	Execution time	Memory
93280		Abelyan	Bomb (IZhO17_bomb)	C++17	100 / 100	476 ms	61688 KiB

bomb

#include <iostream>
#include <algorithm>
#include <climits>
#include <cassert>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
#define fr first
#define sc second
#define FOR(i, a) for (int i = 0; i < (a); i++)
#define F0R(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i,a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)
 
const int N = 2506;
char c[N][N];
int prdz[N][N], praj[N][N], ans1, ans2, pr[N];
 
void ad(int a, int b){
	if (a > ans2)return;
	if (b > ans1)b = ans1;
	pr[a] = min(pr[a], b);
}
 
int main(){
	ios_base::sync_with_stdio(false);
	//freopen("tests/01", "r", stdin);
	int n, m;
	cin >> n >> m;
	//assert(n == 1 && m == 20);
	for (int i = 0; i<n; i++){
		//if (i == 56)cout << "hi" << endl;
		cin >> c[i];
		pr[i] = INT_MAX;
	}
	pr[n] = INT_MAX;
	int mn = INT_MAX;
	for (int i = 0; i<n; i++){
		int tv = 0;
		for (int j = 0; j<m; j++){
			if (c[i][j] == '1'){
				if (j == 0)prdz[i][j] = 1;
				else prdz[i][j] = prdz[i][j - 1] + 1;
				tv++;
			}
			else if (tv != 0){
				mn = min(mn, tv);
				tv = 0;
			}
		}
		for (int j = m - 1; j >= 0; j--){
			if (c[i][j] == '1'){
				praj[i][j] = praj[i][j + 1] + 1;
			}
		}
		//if (tv == 3)cout <<i<< endl;
		if (tv != 0)mn = min(mn, tv);
	}
	ans1 = mn;
	mn = INT_MAX;
	for (int j = 0; j<m; j++){
		int tv = 0;
		for (int i = 0; i<n; i++){
			if (c[i][j] == '1'){
				tv++;
			}
			else if (tv != 0){
				mn = min(mn, tv);
				tv = 0;
			}
		}
		if (tv != 0)mn = min(mn, tv);
	}
	ans2 = mn;
	//cout << ans1 << " " << ans2 << endl;
	//cout << c[31] << endl;
	for (int j = 0; j < m; j++){
		for (int i = 0; i < n; i++){
			if (c[i][j] == '1'){
				int ansaj = INT_MAX,ansdz=INT_MAX, k = 0;
				while (i<n && c[i][j] == '1'){
					k++;
					ansaj = min(ansaj, praj[i][j]);
                  	ansdz = min(ansdz, prdz[i][j]);
					//if (ans == 1 && k<=3)cout << i << " " << j << " " << praj[i][j] << " " << k << endl;
					ad(k, ansaj+ansdz-1);
					i++;
				}
				i--;
			}
		}
	}
	for (int j = 0; j<m; j++){
		for (int i = n - 1; i >= 0; i--){
			if (c[i][j] == '1'){
				int ansdz = INT_MAX,ansaj=INT_MAX, k = 0;
				while (i>=0 && c[i][j] == '1'){
					k++;
					ansaj = min(ansaj, praj[i][j]);
                  	ansdz = min(ansdz, prdz[i][j]);
					//if (ans == 1 && k<=3)cout << i << " " << j << " " << praj[i][j] << " " << k << endl;
					ad(k, ansaj+ansdz-1);
					i--;
				}
				i++;
			}
		}
	}
	int verj = 1;
	for (int i = 1; i <= n; i++){
		if (pr[i] == INT_MAX)continue;
		verj = max(verj, i*pr[i]);
		//cout << pr[i] << endl;
	}
	cout << verj << endl;
	return 0;
}

• Subtask 1: 100 / 100