Submission #91544

#	Time	Username	Problem	Language	Result	Execution time	Memory
91544		davitmarg	Bomb (IZhO17_bomb)	C++17	18 / 100	934 ms	99072 KiB

bomb

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;

int n, m,w,h,l,r,mid;
int mp[2503][2503],pr[2503][2503];
char tmp;

int sum(int ys,int xs,int y,int x)
{
	xs--;
	ys--;
	return pr[y][x] - pr[y][xs] - pr[ys][x] + pr[ys][xs];
}

bool check(int x)
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (mp[i][j] && !mp[i - 1][j] && !mp[i][j - 1])
			{
				int s = sum(i, j, i + x - 1, j + w - 1);
				if (s != x * w)
					return 0;
			}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (mp[i][j] && !mp[i + 1][j] && !mp[i][j + 1])
			{
				int s = sum(i-x+1,j-w+1,i, j);
				if (s != x * w)
					return 0;
			}


	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (mp[i][j] && !mp[i - 1][j] && !mp[i][j + 1])
			{
				int s = sum(i, j - w + 1, i + x - 1, j);
				if (s != x * w)
					return 0;
			}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (mp[i][j] && !mp[i + 1][j] && !mp[i][j - 1])
			{
				int s = sum(i - x + 1, j, i, j + w - 1);
				if (s != x * w)
					return 0;
			}

	return 1;
}

int main()
{
	cin >> n >> m;
	w = m;
	h = n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> tmp;
			mp[i][j] = tmp - '0';
			pr[i][j] = pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1]+mp[i][j];
		}
	for (int i = 1; i <= n; i++)
	{
		int sum = 0;
		for (int j = 1; j <= m; j++)
		{
			sum += mp[i][j];
			if (mp[i][j] == 0)
			{
				if (sum)
					w = min(sum,w);
				sum = 0;
			}
		}
		if(sum)
			w = min(sum, w);
	}

	r = n;
	l = 1;
	h = 1;
	while (l <= r)
	{
		mid = (l + r) / 2;
		if (check(mid))
		{
			h = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}

	cout << max(w * h,1) << endl;
	return 0;
}


/*



5 6
000000
111110
111111
111111
000000


7 8
01001110
01001110
01001100
00000000
01000000
01000000
01000000



7 8
01000000
00000000
00000000
00000000
00000000
00000000
00000000

7 8
11111111
11111111
11111111
11100111
11111111
11111111
11111111

7 8
00000000
00011000
00011000
00000000
00011111
00011111
00000000

*/

• Subtask 1: 18 / 100