oj.uz

Submission #1017451

# Submission time Handle Problem Language Result Execution time Memory
1017451 2024-07-09T08:07:03 Z Gray Bomb (IZhO17_bomb) C++17
31 / 100
 149 ms 131072 KB 
#include <cassert>
#include <iostream>
#include <vector>
#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<ll>> a(n+1, vector<ll>(m+1)), left(n+1, vector<ll>(m+2)), right(n+1, vector<ll>(m+2));
	for (ll i=1; i<=n; i++) 
		for (ll j=1; j<=m; j++){
			char x; cin >> x;
			a[i][j]=x-'0';
		}
	vector<ll> mxwid(n+1, 2e18);
	for (ll i=1; i<=n; i++) {
		for (ll j=1; j<=m; j++){
			left[i][j] = a[i][j]?left[i][j-1]+1:0;
		}
		for (ll j=m; j>=1; j--){
			right[i][j] = a[i][j]?right[i][j+1]+1:0;
			if (a[i][j])mxwid[1]=min(mxwid[1], right[i][j]+left[i][j]-1);
		}
	}
	ll mxh=2e18;
	for (ll j=1; j<=m; j++){
		ll l=m, r=m, cc=0;
		for (ll i=1; i<=n; i++){
			if (a[i][j]){
				l=min(l, left[i][j]);
				r=min(r, right[i][j]);
				cc++;
				mxwid[cc]=min(mxwid[cc], l+r-1);
			}else{
				if (cc)mxh=min(mxh, cc);
				cc=0;
				l=m; r=m;
			}
		}
		if (cc) mxh=min(mxh, cc);
	}
	for (ll j=m; j>=1; j--){
		ll l=m, r=m, cc=0;
		for (ll i=1; i<=n; i++){
			if (a[i][j]){
				l=min(l, left[i][j]);
				r=min(r, right[i][j]);
				cc++;
				mxwid[cc]=min(mxwid[cc], l+r-1);
			}else{
				if (cc) mxh=min(mxh, cc);
				cc=0;
				l=m; r=m;
			}
		}
		if (cc) mxh=min(mxh, cc);
	}
	ll ans=0;
	for (ll i=1; i<=mxh; i++){
		// cout << i << ":" << mxwid[i] << ln;
		if (i>1) mxwid[i]=min(mxwid[i-1], mxwid[i]);
		ans=max(ans, mxwid[i]*i);
	}
	cout << ans << ln;
}
void setIO(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
int main(){
	setIO();
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

Subtask #1
31.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 388 KB Output isn't correct
10 Correct 0 ms 420 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 604 KB Output isn't correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Incorrect 0 ms 720 KB Output isn't correct
24 Incorrect 0 ms 604 KB Output isn't correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 3 ms 3164 KB Output is correct
29 Correct 4 ms 3932 KB Output is correct
30 Incorrect 5 ms 5084 KB Output isn't correct
31 Incorrect 6 ms 4188 KB Output isn't correct
32 Incorrect 6 ms 4188 KB Output isn't correct
33 Correct 5 ms 5468 KB Output is correct
34 Correct 2 ms 2392 KB Output is correct
35 Incorrect 7 ms 5500 KB Output isn't correct
36 Correct 8 ms 5468 KB Output is correct
37 Incorrect 0 ms 348 KB Output isn't correct
38 Runtime error 67 ms 131072 KB Execution killed with signal 9
39 Incorrect 1 ms 348 KB Output isn't correct
40 Correct 27 ms 19364 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Runtime error 48 ms 131072 KB Execution killed with signal 9
44 Correct 6 ms 5468 KB Output is correct
45 Runtime error 48 ms 131072 KB Execution killed with signal 9
46 Runtime error 48 ms 131072 KB Execution killed with signal 9
47 Runtime error 51 ms 131072 KB Execution killed with signal 9
48 Runtime error 50 ms 131072 KB Execution killed with signal 9
49 Runtime error 50 ms 131072 KB Execution killed with signal 9
50 Runtime error 52 ms 131072 KB Execution killed with signal 9
51 Runtime error 60 ms 131072 KB Execution killed with signal 9
52 Runtime error 50 ms 131072 KB Execution killed with signal 9
53 Runtime error 57 ms 131072 KB Execution killed with signal 9
54 Runtime error 58 ms 131072 KB Execution killed with signal 9
55 Runtime error 65 ms 131072 KB Execution killed with signal 9
56 Runtime error 55 ms 131072 KB Execution killed with signal 9
57 Runtime error 70 ms 131072 KB Execution killed with signal 9
58 Runtime error 56 ms 131072 KB Execution killed with signal 9
59 Runtime error 75 ms 131072 KB Execution killed with signal 9
60 Runtime error 57 ms 131072 KB Execution killed with signal 9
61 Runtime error 56 ms 131072 KB Execution killed with signal 9
62 Runtime error 55 ms 131072 KB Execution killed with signal 9
63 Runtime error 55 ms 131072 KB Execution killed with signal 9
64 Runtime error 68 ms 131072 KB Execution killed with signal 9
65 Runtime error 69 ms 131072 KB Execution killed with signal 9
66 Runtime error 55 ms 131072 KB Execution killed with signal 9
67 Runtime error 55 ms 131072 KB Execution killed with signal 9
68 Runtime error 71 ms 131072 KB Execution killed with signal 9
69 Runtime error 58 ms 131072 KB Execution killed with signal 9
70 Incorrect 149 ms 98588 KB Output isn't correct
71 Runtime error 54 ms 131072 KB Execution killed with signal 9
72 Runtime error 61 ms 131072 KB Execution killed with signal 9
73 Runtime error 57 ms 131072 KB Execution killed with signal 9
74 Runtime error 59 ms 131072 KB Execution killed with signal 9
75 Runtime error 53 ms 131072 KB Execution killed with signal 9
76 Runtime error 52 ms 131072 KB Execution killed with signal 9
77 Runtime error 59 ms 131072 KB Execution killed with signal 9
78 Runtime error 52 ms 131072 KB Execution killed with signal 9
79 Runtime error 51 ms 131072 KB Execution killed with signal 9
80 Runtime error 50 ms 131072 KB Execution killed with signal 9
81 Runtime error 53 ms 131072 KB Execution killed with signal 9
82 Runtime error 56 ms 131072 KB Execution killed with signal 9
83 Runtime error 52 ms 131072 KB Execution killed with signal 9
84 Runtime error 52 ms 131072 KB Execution killed with signal 9
85 Runtime error 52 ms 131072 KB Execution killed with signal 9
86 Runtime error 55 ms 131072 KB Execution killed with signal 9
87 Runtime error 57 ms 131072 KB Execution killed with signal 9
88 Runtime error 55 ms 131072 KB Execution killed with signal 9
89 Runtime error 59 ms 131072 KB Execution killed with signal 9
90 Incorrect 130 ms 98584 KB Output isn't correct
91 Runtime error 51 ms 131072 KB Execution killed with signal 9
92 Runtime error 52 ms 131072 KB Execution killed with signal 9
93 Runtime error 58 ms 131072 KB Execution killed with signal 9
94 Runtime error 51 ms 131072 KB Execution killed with signal 9
95 Runtime error 55 ms 131072 KB Execution killed with signal 9
96 Runtime error 54 ms 131072 KB Execution killed with signal 9
97 Runtime error 50 ms 131072 KB Execution killed with signal 9
98 Runtime error 58 ms 131072 KB Execution killed with signal 9
99 Runtime error 57 ms 131072 KB Execution killed with signal 9
100 Runtime error 51 ms 131072 KB Execution killed with signal 9