Submission #833693

#	Time	Username	Problem	Language	Result	Execution time	Memory
833693		vjudge1	Bomb (IZhO17_bomb)	C++17	24 / 100	66 ms	56192 KiB

bomb

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

// // PBDS Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//
//template <class T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
//using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

// Preset
const int maxn = 200000;
const int INF = INT_MAX;
const long long int LINF = LLONG_MAX;
const long long int mod = 1e9 + 7;
const long long int mod2 = 998244353;
//const double e = 2.71828;
const double PI = acos(-1);
const double eps = 1e-10;
#define pb push_back
#define ll long long
#define ull unsigned long long
typedef pair<char,char> pc;
typedef pair<double,double> pd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<pi,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<string,int> psi;
typedef pair<int,string> pis;
typedef pair<char,int> pci;
typedef pair<int,char> pic;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
int dr[4] = {0,1,0,-1}, dc[4] = {1,0,-1,0};


void solve() {
	int n,m;
	cin >> n >> m;
	string s[n+5];
	for (int i=0; i<n; i++) {
		cin >> s[i];
	}
	int pr[m+5][n+5], pc[n+5][m+5];
	int h=n, w=m;
	for (int i=0; i<n; i++) {
		pc[i][0] = (int)(s[i][0]-'0');
		for (int j=1; j<m; j++) {
			if (s[i][j]=='1') pc[i][j] = pc[i][j-1] + 1;
			else {
				if (pc[i][j-1]) w = min(w, pc[i][j-1]);
				pc[i][j] = 0;
			}
		}
		if (pc[i][m-1]) w = min(w, pc[i][m-1]);
	}
	for (int i=0; i<m; i++) {
		pr[i][0] = (int)(s[0][i]-'0');
		for (int j=1; j<n; j++) {
			if (s[j][i]=='1') pr[i][j] = pr[i][j-1] + 1;
			else {
				if (pr[i][j-1]) h = min(h, pr[i][j-1]);
				pr[i][j] = 0;
			}
		}
		if (pr[i][n-1]) h = min(h, pr[i][n-1]);
	}
//	cout << endl;
//	for (int i=0; i<n; i++) {
//		for (int j=0; j<m; j++) cout << pc[i][j] << ' ';
//		cout << endl;
//	}
//	cout << endl;
//	for (int i=0; i<m; i++) {
//		for (int j=0; j<n; j++) cout << pr[i][j] << ' ';
//		cout << endl;
//	}
	int ans = h*w;
	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	precompute();
//	FFT::init_fft();
	int tc=1;
//	cin >> tc;
//	getchar();
//	int idx = 0;
	while (tc--) solve();
 	return 0;
}

• Subtask 1: 24 / 100