oj.uz

Submission #833879

# Submission time Handle Problem Language Result Execution time Memory
833879 2023-08-22T09:17:18 Z vjudge1 Bomb (IZhO17_bomb) C++17
0 / 100
 1000 ms 131072 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<int> &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);
	t[i][v] = t[i][2*v] + t[i][2*v+1];
}

// update
void update(int i, int v, int st, int en, int l, int r, int val) {
	if (lazy[v] != 0) {
		t[i][v] = (en - st + 1) * lazy[i][v];
		
		if (st != en) {
			lazy[i][2*v] = lazy[i][v];
			lazy[i][2*v+1] = lazy[i][v];
		}
		lazy[i][v] = 0;
	}

  	if ((en < l) || (st > r)) {
   	 	return;
  	}

	if (st >= l && en <= r) {
	    t[i][v] = (en - st + 1) * val;
	    if (st != en) {
	      lazy[i][2*v] = val; 
	      lazy[i][2*v+1] = val;
	    }
	    return;
	}

	int mid = (st + en) / 2;
	update(i,2*v, st, mid, l, r, val);
	update(i,2*v+1, mid + 1, en, l, r, val);
	t[i][v] = (t[i][2*v] + t[i][2*v+1]);
}

// query
int query(int i, int v, int st, int en, int l, int r) {
	if (lazy[v] != 0) {
		t[i][v] = (en - st + 1) * lazy[i][v];
		if (st != en) {
	 		lazy[i][2*v] = lazy[i][v];
	  		lazy[i][2*v+1] = lazy[i][v];
		}
		lazy[i][v] = 0;
	}
	
	if (en < l || st > r) {
		return 0;
	}
	
	if ((l <= st) && (en <= r)) {
		return t[i][v];
	}
	
	int mid = (st + en) / 2;
	ll q1 = query(i, 2*v, st, mid, l, r);
	ll q2 = query(i, 2*v+1, mid + 1, en, l, r);
	return (q1 + q2);
}


void solve() {
	int n,m;
	cin >> n >> m;
	string s[n+5];
	for (int i=0; i<n; i++) {
		cin >> s[i];
	}
	vector<vector<int>> a(n+1, vector<int>(m+1)), b(m+1, vector<int>(n+1)), ps(n+1, vector<int>(m+1,0));
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			a[i+1][j+1] = (int)(s[i][j] - '0');
		}
	}
	for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
			b[i+1][j+1] = (int)(s[j][i] - '0');
		}
	}
	for (int i=1; i<=n; i++) ps[i][1] = a[i][1];
	for (int i=1; i<=m; i++) ps[1][i] = 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;
		for (int i=1; i<=m; i++) {
			build(i,b[i],1,1,n);
		}
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n-mid; j++) {
				int area = ps[j+mid][i] - ps[j-1][i];
				if (area == mid) {
					update(i,1,1,n,j,j+mid,0);
				}
			}
		}
		int sum = 0;
		for (int i=1; i<=m; i++) sum += query(i,1,1,n,1,n);
		cout << "height = " << mid << ' ' << sum << endl;
		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;
		for (int i=1; i<=n; i++) {
			build(i,a[i],1,1,m);
			for (int j=1; j<=m; j++) cout << query(i,1,1,m,j,j) << ' ';
			cout << endl;
		}
		cout << endl;
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m-mid; j++) {
				int area = ps[i][j+mid] - ps[i][j-1];
				if (area == mid) {
					update(i,1,1,m,j,j+mid,0);
				}
			}
		}
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m; j++) cout << query(i,1,1,m,j,j) << ' ';
			cout << endl;
		}
		int sum = 0;
		for (int i=1; i<=m; i++) sum += query(i,1,1,m,1,m);
		cout << "width = " << mid << ' ' << sum << endl;
		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 Incorrect 1 ms 468 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Incorrect 23 ms 21076 KB Output isn't correct
4 Incorrect 23 ms 21072 KB Output isn't correct
5 Incorrect 20 ms 21108 KB Output isn't correct
6 Incorrect 7 ms 8520 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 468 KB Output isn't correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 Incorrect 1 ms 464 KB Output isn't correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 452 KB Output isn't correct
14 Incorrect 1 ms 468 KB Output isn't correct
15 Incorrect 1 ms 468 KB Output isn't correct
16 Incorrect 1 ms 468 KB Output isn't correct
17 Incorrect 8 ms 1108 KB Output isn't correct
18 Incorrect 7 ms 1236 KB Output isn't correct
19 Incorrect 13 ms 1492 KB Output isn't correct
20 Incorrect 14 ms 1492 KB Output isn't correct
21 Incorrect 8 ms 1364 KB Output isn't correct
22 Incorrect 15 ms 1492 KB Output isn't correct
23 Incorrect 17 ms 1688 KB Output isn't correct
24 Incorrect 11 ms 1356 KB Output isn't correct
25 Incorrect 18 ms 1748 KB Output isn't correct
26 Incorrect 17 ms 1752 KB Output isn't correct
27 Incorrect 198 ms 8988 KB Output isn't correct
28 Incorrect 291 ms 11888 KB Output isn't correct
29 Incorrect 327 ms 12848 KB Output isn't correct
30 Incorrect 488 ms 16640 KB Output isn't correct
31 Incorrect 423 ms 14656 KB Output isn't correct
32 Incorrect 436 ms 14852 KB Output isn't correct
33 Incorrect 520 ms 17720 KB Output isn't correct
34 Incorrect 181 ms 8840 KB Output isn't correct
35 Incorrect 521 ms 17764 KB Output isn't correct
36 Incorrect 518 ms 17700 KB Output isn't correct
37 Incorrect 2 ms 468 KB Output isn't correct
38 Runtime error 114 ms 131072 KB Execution killed with signal 9
39 Incorrect 2 ms 468 KB Output isn't correct
40 Execution timed out 1038 ms 44904 KB Time limit exceeded
41 Incorrect 1 ms 468 KB Output isn't correct
42 Incorrect 18 ms 1748 KB Output isn't correct
43 Runtime error 116 ms 131072 KB Execution killed with signal 9
44 Incorrect 546 ms 17692 KB Output isn't correct
45 Runtime error 115 ms 131072 KB Execution killed with signal 9
46 Runtime error 115 ms 131072 KB Execution killed with signal 9
47 Runtime error 123 ms 131072 KB Execution killed with signal 9
48 Runtime error 113 ms 131072 KB Execution killed with signal 9
49 Runtime error 116 ms 131072 KB Execution killed with signal 9
50 Runtime error 114 ms 131072 KB Execution killed with signal 9
51 Runtime error 120 ms 131072 KB Execution killed with signal 9
52 Runtime error 115 ms 131072 KB Execution killed with signal 9
53 Runtime error 113 ms 131072 KB Execution killed with signal 9
54 Runtime error 115 ms 131072 KB Execution killed with signal 9
55 Runtime error 119 ms 131072 KB Execution killed with signal 9
56 Runtime error 115 ms 131072 KB Execution killed with signal 9
57 Runtime error 112 ms 131072 KB Execution killed with signal 9
58 Runtime error 114 ms 131072 KB Execution killed with signal 9
59 Runtime error 114 ms 131072 KB Execution killed with signal 9
60 Runtime error 115 ms 131072 KB Execution killed with signal 9
61 Runtime error 114 ms 131072 KB Execution killed with signal 9
62 Runtime error 114 ms 131072 KB Execution killed with signal 9
63 Runtime error 116 ms 131072 KB Execution killed with signal 9
64 Runtime error 118 ms 131072 KB Execution killed with signal 9
65 Runtime error 126 ms 131072 KB Execution killed with signal 9
66 Runtime error 113 ms 131072 KB Execution killed with signal 9
67 Runtime error 113 ms 131072 KB Execution killed with signal 9
68 Runtime error 116 ms 131072 KB Execution killed with signal 9
69 Runtime error 117 ms 131072 KB Execution killed with signal 9
70 Execution timed out 1048 ms 131072 KB Time limit exceeded
71 Runtime error 111 ms 131072 KB Execution killed with signal 9
72 Runtime error 111 ms 131072 KB Execution killed with signal 9
73 Runtime error 113 ms 131072 KB Execution killed with signal 9
74 Runtime error 118 ms 131072 KB Execution killed with signal 9
75 Runtime error 114 ms 131072 KB Execution killed with signal 9
76 Runtime error 113 ms 131072 KB Execution killed with signal 9
77 Runtime error 117 ms 131072 KB Execution killed with signal 9
78 Runtime error 117 ms 131072 KB Execution killed with signal 9
79 Runtime error 115 ms 131072 KB Execution killed with signal 9
80 Runtime error 117 ms 131072 KB Execution killed with signal 9
81 Runtime error 112 ms 131072 KB Execution killed with signal 9
82 Runtime error 120 ms 131072 KB Execution killed with signal 9
83 Runtime error 115 ms 131072 KB Execution killed with signal 9
84 Runtime error 113 ms 131072 KB Execution killed with signal 9
85 Runtime error 121 ms 131072 KB Execution killed with signal 9
86 Runtime error 114 ms 131072 KB Execution killed with signal 9
87 Runtime error 115 ms 131072 KB Execution killed with signal 9
88 Runtime error 113 ms 131072 KB Execution killed with signal 9
89 Runtime error 119 ms 131072 KB Execution killed with signal 9
90 Execution timed out 1046 ms 131072 KB Time limit exceeded
91 Runtime error 113 ms 131072 KB Execution killed with signal 9
92 Runtime error 108 ms 131072 KB Execution killed with signal 9
93 Runtime error 119 ms 131072 KB Execution killed with signal 9
94 Runtime error 115 ms 131072 KB Execution killed with signal 9
95 Runtime error 113 ms 131072 KB Execution killed with signal 9
96 Runtime error 117 ms 131072 KB Execution killed with signal 9
97 Runtime error 111 ms 131072 KB Execution killed with signal 9
98 Runtime error 114 ms 131072 KB Execution killed with signal 9
99 Runtime error 116 ms 131072 KB Execution killed with signal 9
100 Runtime error 116 ms 131072 KB Execution killed with signal 9