Submission #93208

#	Time	Username	Problem	Language	Result	Execution time	Memory
93208		Vardanyan	Bomb (IZhO17_bomb)	C++14	28 / 100	271 ms	109228 KiB

bomb

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2505;
int dzaxic[N][N];
int ajic[N][N];
int a[N][N];
int n, m;
int M[N];
int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			char c;
			cin >> c;
			a[i][j] = c - '0';
		}
	}
	int mnw = 1000*1000*1000+5;
	int mnh = mnw;
	for (int i = 1; i <= n; i++)
	{
		int now = 0;
		for (int j = 1; j <= m; j++){
			if (a[i][j]){
				now++;
				dzaxic[i][j] = now;
			}
			else{
			if(now)	mnw = min(mnw, now);
				now = 0;
			}
		}
		now = 0;
		for (int j = m; j >= 1; j--){
			if (a[i][j]){
				now++;
				ajic[i][j] = now;
			}
			else now = 0;
		}
	}
	for (int j = 1; j <= m; j++){
			int now = 0;
		for (int i = 1; i <= n; i++){
			if (a[i][j]){
				now++;
			}
			else{
			if(now)	mnh = min(mnh, now);
				now = 0;
			}
		}
	}
	//cout << mnh << " " << mnw << endl;
	/*for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cout <<ajic[i][j] << " ";
		}
		cout << endl;
	}*/
	vector<pair<int, int> > v;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (a[i][j] == 1 && a[i - 1][j] == 0 && a[i][j - 1] == 0 && a[i - 1][j - 1] == 0){
				int now = -1;
				for (int ii = i; ii <= n; ii++){
					if (now == -1 || ajic[ii][j] < now){
						now = ajic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ ii - i + 1, now });
				}
			}
			if (a[i][j] == 1 && a[i][j - 1] == 0 && a[i + 1][j - 1] == 0 && a[i][j + 1] == 0){
				int now = -1;
				for (int ii = i; ii >= 1; ii--){
					if (now == -1 || ajic[ii][j] < now){
						now = ajic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ i - ii + 1, now });
				}
			}
			if (a[i][j] == 1 && a[i - 1][j] == 0 && a[i][j + 1] == 0 && a[i - 1][j + 1] == 0){
				int now = -1;
				for (int ii = i; ii <= n; ii++){
					if (now == -1 || dzaxic[i][j] < now){
						now = dzaxic[i][j];
					}
					now = min(now, mnw);
					v.push_back({ ii - i + 1, now });
				}
			}
			if (a[i][j] == 1 && a[i + 1][j] == 0 && a[i][j + 1] == 0 && a[i + 1][j + 1] == 0){
				int now = -1;
				for (int ii = i; ii >= 1; ii--){
					if (now == -1 || dzaxic[ii][j] < now){
						now = dzaxic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ i - ii + 1, now });
				}
			}
		}
	}
	memset(M, 63, sizeof M);
	for (int i = 0; i < v.size(); i++){
		int a = v[i].first;
		int b = v[i].second;
		M[a] = min(M[a], b);
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++){
		long long a = i;
		long long b = M[i];
		a *= b;
		ans = max(ans, a);
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:35:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(now) mnw = min(mnw, now);
    ^~
bomb.cpp:36:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     now = 0;
     ^~~
bomb.cpp:55:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(now) mnh = min(mnh, now);
    ^~
bomb.cpp:56:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     now = 0;
     ^~~
bomb.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~

• Subtask 1: 28 / 100