Submission #833797

#	Time	Username	Problem	Language	Result	Execution time	Memory
833797		vjudge1	Bomb (IZhO17_bomb)	C++17	24 / 100	403 ms	58260 KiB

bomb

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

int dpHorizontal[2505][2505] = {0}; 
int dpVertical[2505][2505] = {0}; 

int main()
{
	int n, m; 
	cin >> n >> m; 
	char arr[n + 5][m + 5]; 
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> arr[i][j]; 
		}
	}
	int res = 0; 
	int sum = 0; 
	if(n == 1 || m == 1)
	{
		if(n == 1)
		{
			for(int i = 0; i < m; i++)
			{
//				cout << res << " "; 
				if(arr[0][i] == '1')
				{
					sum++; 
				}
				else
				{
					if(res == 0)res = sum; 
					else if(res > 0 && sum > 0)
					{
						res = min(res, sum); 
					}
					sum = 0; 
				}
			}
			if(res == 0)res = sum; 
			else if(res > 0 && sum > 0) res = min(res, sum); 
	
		}
		else if(m == 1)
		{
			for(int i = 0; i < n; i++)
			{
//				cout << sum << " "; 
				if(arr[i][0] == '1')
				{
					sum++; 
				}
				else
				{
					if(res == 0)res = sum; 
					else if(res > 0 && sum > 0)
					{
						res = min(res, sum); 
					}
					sum = 0; 
				}
			}
			if(res == 0)res = sum; 
			else if(res > 0 && sum > 0)res = min(res, sum); 
		}
	}
	else
	{
		
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				if(arr[i - 1][j - 1] == '1')
				{
					dpHorizontal[i][j] = dpHorizontal[i][j - 1] + 1; 
				}
			}
		}
		
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(arr[j - 1][i - 1] == '1')
				{
					dpVertical[j][i] = dpVertical[j - 1][i] + 1; 
				}
			}
		}
		
//		for(int i = 0; i <= n; i++)
//		{
//			for(int j = 0; j <= m; j++)
//			{
//				cout << dpVertical[i][j] << " "; 
//			}
//			cout << endl; 
//		}
		
		int minHorizontal = -1; 
     	for(int i = 1; i <= n; i++)
     	{
     		for(int j = 1; j <= m; j++)
     		{
     			if(dpHorizontal[i][j + 1] == 0 && dpHorizontal[i][j] > 0)
     	      	{
     		    	if(minHorizontal == -1)
     		    	{
     		    		minHorizontal = dpHorizontal[i][j]; 
			    	}
			    	else minHorizontal = min(minHorizontal, dpHorizontal[i][j]); 
		     	}
			}
		}
//		cout << minHorizontal << endl; 
		int minVertical = -1; 
		for(int i = 1; i <= m; i++)
     	{
     		for(int j = 1; j <= n; j++)
     		{
     			if(dpVertical[j + 1][i] == 0  && dpVertical[j][i] > 0)
     	      	{
     		    	if(minVertical == -1)
     		    	{
     		    		minVertical = dpVertical[j][i]; 
			    	}
			    	else minVertical= min(minVertical, dpVertical[j][i]); 
		     	}
			}
		}
		res = minHorizontal * minVertical; 
		
	}

	cout << res << endl; 
	return 0; 
}

• Subtask 1: 24 / 100