Submission #334560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334560	2020-12-09T12:02:11 Z	tengiz05	Bomb (IZhO17_bomb)	C++17	81 / 100	332 ms	89068 KB

bomb

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2505;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N][N], n, m, k;
bool usedup[N][N], usedr[N][N];
int up[N][N], down[N][N];
int ans[N];
vector<int> v[N];
vector<int> s[N];
void solve(int test_case){
	int i, j;
	cin >> n >> m;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			char c;
			cin >> c;
			a[i][j] = (c-'0');
		}
	}
	int mx=mod, my=mod;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j] == 1){
				if(usedup[i][j])continue;
				int t = j;
				int tmp = 0;
				while(t <= m && a[i][t] == 1){
					tmp++;
					usedup[i][t] = true;
					t++;
				}mx = min(mx, tmp);
			}
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(a[i][j] == 1){
				if(usedr[i][j])continue;
				int t = i;
				int tmp = 0;
				while(t <= n && a[t][j] == 1){
					tmp++;
					usedr[t][j] = true;
					t++;
				}my = min(my, tmp);
			}
		}
	}
	if(mx == mod){
		mx = 0;
		my = 0;
	}
	
	/// (mx, my) is greedy answer
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			up[i][j] = up[i-1][j]+a[i][j];
		}
	}
	for(i=n;i>=1;i--){
		for(j=1;j<=m;j++){
			down[i][j] = down[i+1][j]+a[i][j];
		}
	}
	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(!a[i][j])continue;
			int cnt = 1;
			int tmp = j;
			while(j+1 <= m && a[i][j+1])cnt++,j++;
			v[i].pb(tmp);
			s[i].pb(cnt);
		}
	}
	for(i=1;i<=m;i++)ans[i] = my;
	for(i=1;i<=n;i++){
		for(k=0;k<v[i].size();k++){
			int j = v[i][k];
			int sz = s[i][k];
			int a=mod, b=mod, c=0;
			for(;sz;sz--, j++){
				a = min(a, up[i][j]);
				b = min(b, down[i][j]);
				c++;
				ans[c] = min(ans[c], a+b-1);
			}
		}
		
		for(k=(int)v[i].size()-1;k>=0;k--){
			int sz = s[i][k];
			int j = v[i][k]+sz-1;
			int a=mod, b=mod, c=0;
			for(;sz;sz--, j--){
				a = min(a, up[i][j]);
				b = min(b, down[i][j]);
				c++;
				ans[c] = min(ans[c], a+b-1);
			}
		}
		
	}
//	cout << mx << ' ' << my << '\n';
	for(i=2;i<=mx;i++)ans[i] = min(ans[i], ans[i-1]);
	int res = 0;
//	for(i=1;i<=mx;i++)cout << ans[i] << ' '; cout << '\n';
	for(i=1;i<=mx;i++)res = max(res, i*ans[i]);
	cout << res << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}
/*

6 6
000111
011111
011111
111000
111000
111000


*/

Compilation message

bomb.cpp: In function 'void solve(int)':
bomb.cpp:88:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(k=0;k<v[i].size();k++){
      |           ~^~~~~~~~~~~~

Subtask #1

81.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	748 KB	Output is correct
3	Correct	25 ms	42988 KB	Output is correct
4	Correct	25 ms	42988 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	1 ms	748 KB	Output is correct
9	Correct	1 ms	748 KB	Output is correct
10	Correct	1 ms	748 KB	Output is correct
11	Correct	1 ms	876 KB	Output is correct
12	Correct	1 ms	748 KB	Output is correct
13	Correct	1 ms	748 KB	Output is correct
14	Correct	1 ms	748 KB	Output is correct
15	Correct	1 ms	748 KB	Output is correct
16	Correct	1 ms	876 KB	Output is correct
17	Correct	1 ms	1644 KB	Output is correct
18	Incorrect	1 ms	1516 KB	Output isn't correct
19	Correct	2 ms	2028 KB	Output is correct
20	Correct	2 ms	2028 KB	Output is correct
21	Correct	1 ms	1260 KB	Output is correct
22	Incorrect	1 ms	1644 KB	Output isn't correct
23	Correct	2 ms	2156 KB	Output is correct
24	Correct	2 ms	1772 KB	Output is correct
25	Correct	2 ms	2284 KB	Output is correct
26	Correct	2 ms	2284 KB	Output is correct
27	Correct	7 ms	6508 KB	Output is correct
28	Incorrect	5 ms	5612 KB	Output isn't correct
29	Incorrect	9 ms	8684 KB	Output isn't correct
30	Correct	10 ms	9580 KB	Output is correct
31	Correct	8 ms	7532 KB	Output is correct
32	Correct	9 ms	8940 KB	Output is correct
33	Correct	11 ms	10604 KB	Output is correct
34	Incorrect	5 ms	6124 KB	Output isn't correct
35	Correct	9 ms	8812 KB	Output is correct
36	Correct	12 ms	10732 KB	Output is correct
37	Correct	1 ms	876 KB	Output is correct
38	Correct	312 ms	87788 KB	Output is correct
39	Correct	1 ms	876 KB	Output is correct
40	Incorrect	40 ms	25196 KB	Output isn't correct
41	Correct	1 ms	896 KB	Output is correct
42	Correct	2 ms	2284 KB	Output is correct
43	Correct	265 ms	87788 KB	Output is correct
44	Correct	11 ms	10732 KB	Output is correct
45	Correct	260 ms	87788 KB	Output is correct
46	Correct	200 ms	88940 KB	Output is correct
47	Correct	277 ms	87788 KB	Output is correct
48	Incorrect	247 ms	87788 KB	Output isn't correct
49	Correct	323 ms	87940 KB	Output is correct
50	Incorrect	251 ms	87788 KB	Output isn't correct
51	Incorrect	254 ms	87788 KB	Output isn't correct
52	Incorrect	248 ms	87788 KB	Output isn't correct
53	Incorrect	247 ms	87788 KB	Output isn't correct
54	Correct	211 ms	87916 KB	Output is correct
55	Incorrect	207 ms	87020 KB	Output isn't correct
56	Correct	322 ms	89068 KB	Output is correct
57	Incorrect	207 ms	85228 KB	Output isn't correct
58	Correct	210 ms	87788 KB	Output is correct
59	Incorrect	204 ms	86508 KB	Output isn't correct
60	Correct	245 ms	87788 KB	Output is correct
61	Correct	317 ms	87920 KB	Output is correct
62	Correct	298 ms	87916 KB	Output is correct
63	Correct	332 ms	87788 KB	Output is correct
64	Correct	210 ms	87788 KB	Output is correct
65	Incorrect	249 ms	87788 KB	Output isn't correct
66	Incorrect	242 ms	87788 KB	Output isn't correct
67	Incorrect	259 ms	87788 KB	Output isn't correct
68	Incorrect	263 ms	87788 KB	Output isn't correct
69	Incorrect	208 ms	84972 KB	Output isn't correct
70	Correct	118 ms	65000 KB	Output is correct
71	Correct	176 ms	83948 KB	Output is correct
72	Correct	184 ms	84716 KB	Output is correct
73	Correct	201 ms	84204 KB	Output is correct
74	Correct	184 ms	85484 KB	Output is correct
75	Correct	191 ms	85996 KB	Output is correct
76	Correct	192 ms	86380 KB	Output is correct
77	Correct	205 ms	86252 KB	Output is correct
78	Correct	192 ms	86508 KB	Output is correct
79	Correct	165 ms	78572 KB	Output is correct
80	Correct	166 ms	79340 KB	Output is correct
81	Correct	167 ms	78700 KB	Output is correct
82	Correct	203 ms	87276 KB	Output is correct
83	Correct	204 ms	87532 KB	Output is correct
84	Correct	159 ms	75756 KB	Output is correct
85	Correct	218 ms	87788 KB	Output is correct
86	Correct	303 ms	87916 KB	Output is correct
87	Correct	197 ms	87916 KB	Output is correct
88	Correct	204 ms	86764 KB	Output is correct
89	Correct	241 ms	87788 KB	Output is correct
90	Correct	127 ms	70636 KB	Output is correct
91	Correct	218 ms	87788 KB	Output is correct
92	Correct	241 ms	87788 KB	Output is correct
93	Correct	298 ms	87788 KB	Output is correct
94	Correct	238 ms	87788 KB	Output is correct
95	Correct	203 ms	87532 KB	Output is correct
96	Correct	202 ms	87404 KB	Output is correct
97	Correct	316 ms	87788 KB	Output is correct
98	Correct	206 ms	87148 KB	Output is correct
99	Correct	239 ms	87916 KB	Output is correct
100	Correct	291 ms	87788 KB	Output is correct