Submission #878865

#	Time	Username	Problem	Language	Result	Execution time	Memory
878865		Gray	Bomb (IZhO17_bomb)	C++17	0 / 100	731 ms	95448 KiB

bomb

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include <cassert>
#define ll long long
#define ln "\n"
#define ff first
#define ss second
#define ld long double
const ll INF = 2e18;
const ll MOD = 1e9+7;
using namespace std;

void solve(){
	ll n, m; cin >> n >> m;
	vector<vector<char>> grid(n, vector<char>(m));
	for (ll i=0; i<n; i++){
		for (ll j=0; j<m; j++) cin >> grid[i][j];
	}
	vector<vector<ll>> dist(n, vector<ll>(m, 0));
	for (ll i=0; i<n; i++){
		ll loj = -1;
		for (ll j=0; j<m; j++){
			if (grid[i][j] == '0'){
				loj = j;
			}
			dist[i][j] = j-loj;
		}
	}
	ll mnw = m, mnh = n;
	for (ll j=0; j<m; j++){
		vector<ll> tpdi(n);
		stack<ll> mni;
		for (ll i=0; i<n; i++){
			while (!mni.empty() and dist[mni.top()][j]>=dist[i][j]) mni.pop();
			if (!mni.empty()) tpdi[i] = i-mni.top();
			else tpdi[i] = i+1;
			mni.push(i);
		}
		mni = stack<ll>();
		for (ll i = n-1; i>=0; i--){
			ll tdp = 0;
			while (!mni.empty() and dist[mni.top()][j]>=dist[i][j]) mni.pop();
			if (!mni.empty()){
				// cout << mni.top() << ln;
				tdp = mni.top()-i;
			}else tdp = n-i;
			mni.push(i);
			if (grid[i][j]=='0') continue;
			mnw = min(mnw, dist[i][j]);
			mnh = min(mnh, tdp+tpdi[i]-1);
			// cout << i << " " << j << ": " << dist[i][j] << " ; " << tdp << " " << tpdi[i] << ln;
		}
	}
	cout << mnw*mnh << ln;
}
void setIO(){
	// ios_base::sync_with_stdio(false);
	// cin.tie(nullptr);
	// cout.tie(nullptr);
    freopen("bomb.in", "r", stdin);
    freopen("bomb.out", "w", stdout);
}
int main(){
	setIO();
	ll t=1;
    // cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

bomb.cpp: In function 'void setIO()':
bomb.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen("bomb.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:62:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen("bomb.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100