Submission #223963

#	Time	Username	Problem	Language	Result	Execution time	Memory
223963		super_j6	Bomb (IZhO17_bomb)	C++14	17 / 100	192 ms	80120 KiB

bomb

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int maxn = 2502;
int n, m;
int a[maxn][maxn], h[maxn][maxn], v[maxn][maxn];
stack<int> stk;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	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 == '1';
		h[i][j] = a[i][j] + h[i][j - 1];
		v[i][j] = a[i][j] + v[i - 1][j];
	}
	
	int x = n, y = m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m + 1; j++){
			a[i][j] = a[i][j] * (a[i - 1][j] + 1);
			while(!stk.empty() && a[i][j] <= a[i][stk.top()]){
				int c = stk.top();
				stk.pop();
				int dx = a[i][c], dy = j - (stk.empty() ? 0 : stk.top()) - 1;
				if(h[i + 1][j - 1] - h[i + 1][j - dy - 1] != dy && v[i][j] - v[i - dx][j] != dx){
					x = min(x, dx), y = min(y, dy);
				}
			}
			stk.push(j);
		}
		while(!stk.empty()) stk.pop();
	}
	
	cout << (x * y) << endl;

	return 0;
}

• Subtask 1: 17 / 100