oj.uz

Submission #834099

# Submission time Handle Problem Language Result Execution time Memory
834099 2023-08-22T10:46:36 Z vjudge1 Bomb (IZhO17_bomb) C++17
0 / 100
 86 ms 131076 KB 
#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 = 10000;
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};

int t[maxn+5][maxn+5], lazy[maxn+5][maxn+5];

// build
void build(int i, vector<ll> &a, int v, int st, int en) {
	if (st == en) {
		t[i][v] = a[st];
		return;
	}
	int mid = (st + en) / 2;
	build(i, a, 2*v, st, mid);
	build(i, a, 2*v+1, mid + 1, en);
}

// push lazy
void push (int i, int v) {
	if (lazy[i][v]) {
		t[i][v*2] = t[i][v*2+1] = t[i][v];
		lazy[i][v*2] = lazy[i][v*2+1] = 1;
		lazy[i][v] = 0;
	}
}

// update
void update(int i, int v, int st, int en, int l, int r, int val) {
	if (l>r) return;
	if (st==l && en==r) {
		t[i][v] = val;
		lazy[i][v] = 1;
	}
	else {
		push(i,v);
		int mid = (st+en)/2;
		update(i,v*2,st,mid,l,min(r,mid),val);
		update(i,v*2+1,mid+1,en,max(l,mid+1),r,val);
	}
}

// query
int query(int i, int v, int st, int en, int p) {
	if (st==en) return t[i][v];
	push(i,v);
	int mid = (st+en)/2;
	if (p<=mid) return query(i, v*2, st, mid, p);
	else return query(i, v*2+1, mid+1, en, p);
}


void solve() {
	ll n,m;
	cin >> n >> m;
	string s[n+5];
	for (ll i=0; i<n; i++) {
		cin >> s[i];
	}
	vector<vector<ll>> a(n+1, vector<ll>(m+1)), b(m+1, vector<ll>(n+1)), ps(n+1, vector<ll>(m+1,0));
	for (ll i=0; i<n; i++) {
		for (ll j=0; j<m; j++) {
			a[i+1][j+1] = (s[i][j]=='0') ? 0ll : 1ll;
		}
	}
	for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
			b[i+1][j+1] = (s[j][i]=='0') ? 0ll : 1ll;
		}
	}
	for (int i=1; i<=n; i++) ps[i][1] = ps[i-1][1] + a[i][1];
	for (int i=1; i<=m; i++) ps[1][i] = ps[1][i-1] + a[1][i];
	for (int i=2; i<=n; i++) {
		for (int j=2; j<=m; j++) {
			ps[i][j] = ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + a[i][j];
		}
	}
	
	int h = 0, w = 0;
	
	// binser for height
	int l = 1, r = n;
	while (l<=r) {
		int mid = l + (r-l)/2;
		memset(lazy,0,sizeof(lazy));
		memset(t,-1,sizeof(t));
		for (int i=1; i<=m; i++) {
			build(i,b[i],1,1,n);
//			for (int j=1; j<=n; j++) cout << query(i,1,1,n,j) << ' ';
//			cout << endl;
		}
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n-mid+1; j++) {
				int area = ps[j+mid-1][i] - ps[j+mid-1][i-1] - ps[j-1][i] + ps[j-1][i-1];
				if (area == mid) {
					update(i,1,1,n,j,j+mid-1,0);
				}
			}
		}
		int sum = 0;
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n; j++) sum += query(i,1,1,n,j);
		}
		if (sum==0) {
			h = max(h, mid);
			l = mid+1;
		}
		else r = mid-1;
	}
	
	// binser for width
	l = 1, r = m;
	while (l<=r) {
		int mid = l + (r-l)/2;
		memset(lazy,0,sizeof(lazy));
		memset(t,-1,sizeof(t));
		for (int i=1; i<=n; i++) {
			build(i,a[i],1,1,m);
		}
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m-mid+1; j++) {
				int area = ps[i][j+mid-1] - ps[i][j-1] - ps[i-1][j+mid-1] + ps[i-1][j-1];
				if (area == mid) {
					update(i,1,1,m,j,j+mid-1,0);
				}
			}
		}
		int sum = 0;
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m; j++) sum += query(i,1,1,m,j);
		}
		if (sum==0) {
			w = max(w, mid);
			l = mid+1;
		}
		else r = mid-1;
	}
	
	int ans = h*w;
	cout << ans << endl;
}

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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 131072 KB Execution killed with signal 9
2 Runtime error 48 ms 131072 KB Execution killed with signal 9
3 Runtime error 46 ms 131072 KB Execution killed with signal 9
4 Runtime error 45 ms 131072 KB Execution killed with signal 9
5 Runtime error 46 ms 131072 KB Execution killed with signal 9
6 Runtime error 45 ms 131072 KB Execution killed with signal 9
7 Runtime error 47 ms 131072 KB Execution killed with signal 9
8 Runtime error 49 ms 131072 KB Execution killed with signal 9
9 Runtime error 45 ms 131072 KB Execution killed with signal 9
10 Runtime error 47 ms 131072 KB Execution killed with signal 9
11 Runtime error 49 ms 131072 KB Execution killed with signal 9
12 Runtime error 47 ms 131072 KB Execution killed with signal 9
13 Runtime error 49 ms 131072 KB Execution killed with signal 9
14 Runtime error 47 ms 131072 KB Execution killed with signal 9
15 Runtime error 46 ms 131072 KB Execution killed with signal 9
16 Runtime error 50 ms 131072 KB Execution killed with signal 9
17 Runtime error 48 ms 131072 KB Execution killed with signal 9
18 Runtime error 47 ms 131072 KB Execution killed with signal 9
19 Runtime error 47 ms 131072 KB Execution killed with signal 9
20 Runtime error 54 ms 131072 KB Execution killed with signal 9
21 Runtime error 47 ms 131072 KB Execution killed with signal 9
22 Runtime error 46 ms 131072 KB Execution killed with signal 9
23 Runtime error 45 ms 131072 KB Execution killed with signal 9
24 Runtime error 45 ms 131072 KB Execution killed with signal 9
25 Runtime error 48 ms 131072 KB Execution killed with signal 9
26 Runtime error 45 ms 131072 KB Execution killed with signal 9
27 Runtime error 47 ms 131072 KB Execution killed with signal 9
28 Runtime error 53 ms 131072 KB Execution killed with signal 9
29 Runtime error 48 ms 131072 KB Execution killed with signal 9
30 Runtime error 48 ms 131072 KB Execution killed with signal 9
31 Runtime error 47 ms 131072 KB Execution killed with signal 9
32 Runtime error 47 ms 131072 KB Execution killed with signal 9
33 Runtime error 48 ms 131072 KB Execution killed with signal 9
34 Runtime error 47 ms 131072 KB Execution killed with signal 9
35 Runtime error 60 ms 131072 KB Execution killed with signal 9
36 Runtime error 50 ms 131072 KB Execution killed with signal 9
37 Runtime error 43 ms 131072 KB Execution killed with signal 9
38 Runtime error 57 ms 131072 KB Execution killed with signal 9
39 Runtime error 46 ms 131072 KB Execution killed with signal 9
40 Runtime error 52 ms 131072 KB Execution killed with signal 9
41 Runtime error 47 ms 131072 KB Execution killed with signal 9
42 Runtime error 45 ms 131072 KB Execution killed with signal 9
43 Runtime error 55 ms 131072 KB Execution killed with signal 9
44 Runtime error 47 ms 131072 KB Execution killed with signal 9
45 Runtime error 57 ms 131072 KB Execution killed with signal 9
46 Runtime error 57 ms 131072 KB Execution killed with signal 9
47 Runtime error 55 ms 131072 KB Execution killed with signal 9
48 Runtime error 57 ms 131072 KB Execution killed with signal 9
49 Runtime error 60 ms 131072 KB Execution killed with signal 9
50 Runtime error 59 ms 131072 KB Execution killed with signal 9
51 Runtime error 57 ms 131072 KB Execution killed with signal 9
52 Runtime error 59 ms 131072 KB Execution killed with signal 9
53 Runtime error 59 ms 131072 KB Execution killed with signal 9
54 Runtime error 55 ms 131072 KB Execution killed with signal 9
55 Runtime error 57 ms 131072 KB Execution killed with signal 9
56 Runtime error 53 ms 131072 KB Execution killed with signal 9
57 Runtime error 56 ms 131072 KB Execution killed with signal 9
58 Runtime error 59 ms 131072 KB Execution killed with signal 9
59 Runtime error 86 ms 131076 KB Execution killed with signal 9
60 Runtime error 57 ms 131072 KB Execution killed with signal 9
61 Runtime error 58 ms 131072 KB Execution killed with signal 9
62 Runtime error 67 ms 131072 KB Execution killed with signal 9
63 Runtime error 60 ms 131072 KB Execution killed with signal 9
64 Runtime error 61 ms 131072 KB Execution killed with signal 9
65 Runtime error 58 ms 131072 KB Execution killed with signal 9
66 Runtime error 60 ms 131072 KB Execution killed with signal 9
67 Runtime error 58 ms 131072 KB Execution killed with signal 9
68 Runtime error 61 ms 131072 KB Execution killed with signal 9
69 Runtime error 57 ms 131072 KB Execution killed with signal 9
70 Runtime error 77 ms 131072 KB Execution killed with signal 9
71 Runtime error 63 ms 131072 KB Execution killed with signal 9
72 Runtime error 56 ms 131072 KB Execution killed with signal 9
73 Runtime error 58 ms 131072 KB Execution killed with signal 9
74 Runtime error 65 ms 131072 KB Execution killed with signal 9
75 Runtime error 67 ms 131072 KB Execution killed with signal 9
76 Runtime error 59 ms 131072 KB Execution killed with signal 9
77 Runtime error 63 ms 131072 KB Execution killed with signal 9
78 Runtime error 65 ms 131072 KB Execution killed with signal 9
79 Runtime error 59 ms 131072 KB Execution killed with signal 9
80 Runtime error 58 ms 131072 KB Execution killed with signal 9
81 Runtime error 60 ms 131072 KB Execution killed with signal 9
82 Runtime error 54 ms 131072 KB Execution killed with signal 9
83 Runtime error 66 ms 131072 KB Execution killed with signal 9
84 Runtime error 63 ms 131072 KB Execution killed with signal 9
85 Runtime error 60 ms 131072 KB Execution killed with signal 9
86 Runtime error 62 ms 131072 KB Execution killed with signal 9
87 Runtime error 60 ms 131072 KB Execution killed with signal 9
88 Runtime error 61 ms 131072 KB Execution killed with signal 9
89 Runtime error 59 ms 131072 KB Execution killed with signal 9
90 Runtime error 77 ms 131072 KB Execution killed with signal 9
91 Runtime error 63 ms 131072 KB Execution killed with signal 9
92 Runtime error 59 ms 131072 KB Execution killed with signal 9
93 Runtime error 62 ms 131072 KB Execution killed with signal 9
94 Runtime error 61 ms 131072 KB Execution killed with signal 9
95 Runtime error 59 ms 131072 KB Execution killed with signal 9
96 Runtime error 61 ms 131072 KB Execution killed with signal 9
97 Runtime error 61 ms 131072 KB Execution killed with signal 9
98 Runtime error 65 ms 131072 KB Execution killed with signal 9
99 Runtime error 61 ms 131072 KB Execution killed with signal 9
100 Runtime error 58 ms 131072 KB Execution killed with signal 9