답안 #93224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93224	2019-01-07T10:08:21 Z	Vardanyan	Bomb (IZhO17_bomb)	C++14	70 / 100	328 ms	104124 KB

bomb

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2505;
int dzaxic[N][N];
int ajic[N][N];
int a[N][N];
int n, m;
int M[N];

int mnw = 1000 * 1000 * 1000 + 5;
int mnh = mnw;
vector<pair<int, int> > v;
int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			char c;
			cin >> c;
			a[i][j] = c - '0';
		}
	}
	for (int i = 1; i <= n; i++)
	{
		int now = 0;
		for (int j = 1; j <= m; j++){
			if (a[i][j]){
				now++;
				dzaxic[i][j] = now;
			}
			else{
				if (now)	mnw = min(mnw, now);
				now = 0;
			}
		}
		if (now)	mnw = min(mnw, now);
		now = 0;
		for (int j = m; j >= 1; j--){
			if (a[i][j]){
				now++;
				ajic[i][j] = now;
			}
			else{
				if (now)	mnw = min(mnw, now);
				now = 0;
			}
		}
		if (now)	mnw = min(mnw, now);
		now = 0;
	}
	for (int j = 1; j <= m; j++){
		int now = 0;
		for (int i = 1; i <= n; i++){
			if (a[i][j]){
				now++;
			}
			else{
				if (now)	mnh = min(mnh, now);
				now = 0;
			}
		}
		if (now)	mnh = min(mnh, now);
	}
	//cout << mnh << " " << mnw << endl;
	/*for (int i = 1; i <= n; i++){
	for (int j = 1; j <= m; j++){
	cout <<ajic[i][j] << " ";
	}
	cout << endl;
	}*/
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (a[i][j] == 1 && a[i - 1][j] == 0 && a[i][j - 1] == 0 && a[i - 1][j - 1] == 0){
				int now = -1;
				//calc1(i, j, 1);
				for (int ii = i; ii <= n; ii++){
					if (a[ii][j] == 0) break;
					if (now == -1 || ajic[ii][j] < now){
						now = ajic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ ii - i + 1, now });
				}
			}
			if (a[i][j] == 1 && a[i][j - 1] == 0 && a[i + 1][j - 1] == 0 && a[i][j + 1] == 0){
				int now = -1;
				//calc1(i, j, -1);
				for (int ii = i; ii >= 1; ii--){
					if (a[ii][j] == 0) break;
					if (now == -1 || ajic[ii][j] < now){
						now = ajic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ i - ii + 1, now });
				}
			}
			if (a[i][j] == 1 && a[i - 1][j] == 0 && a[i][j + 1] == 0 && a[i - 1][j + 1] == 0){
				int now = -1;
				for (int ii = i; ii <= n; ii++){
					if (a[ii][j] == 0) break;
					if (now == -1 || dzaxic[ii][j] < now){
						now = dzaxic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ ii - i + 1, now });
				}
			}
			if (a[i][j] == 1 && a[i + 1][j] == 0 && a[i][j + 1] == 0 && a[i + 1][j + 1] == 0){
				int now = -1;
				for (int ii = i; ii >= 1; ii--){
					if (a[ii][j] == 0) break;
					if (now == -1 || dzaxic[ii][j] < now){
						now = dzaxic[ii][j];
					}
					now = min(now, mnw);
					v.push_back({ i - ii + 1, now });
				}
			}
		}
	}
	//	cout << mnh << " " << mnw << endl;
	memset(M, -1, sizeof M);
	for (int i = 0; i < v.size(); i++){
		int a = v[i].first;
		int b = v[i].second;
		b = min(b, mnw);
		if (M[a] == -1 || M[a] > b){
			M[a] = b;
		}
	}
	int ans = 0;
	for (int i = 0; i < v.size(); i++){
		int a = v[i].first;
		a = min(a, mnh);
		//if (a > mnh) continue;
		int b = M[a];
		a *= b;
		ans = max(ans, a);
	}
	cout << ans << endl;
	return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
bomb.cpp:137:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~

Subtask #1

70.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	60 ms	46932 KB	Output is correct
4	Correct	40 ms	38756 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Incorrect	2 ms	504 KB	Output isn't correct
10	Correct	2 ms	504 KB	Output is correct
11	Incorrect	2 ms	504 KB	Output isn't correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	508 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	632 KB	Output is correct
17	Correct	2 ms	1144 KB	Output is correct
18	Correct	2 ms	1016 KB	Output is correct
19	Incorrect	2 ms	1272 KB	Output isn't correct
20	Correct	2 ms	1272 KB	Output is correct
21	Correct	2 ms	760 KB	Output is correct
22	Correct	2 ms	1016 KB	Output is correct
23	Incorrect	2 ms	1272 KB	Output isn't correct
24	Incorrect	2 ms	1144 KB	Output isn't correct
25	Correct	2 ms	1528 KB	Output is correct
26	Correct	2 ms	1656 KB	Output is correct
27	Correct	6 ms	4856 KB	Output is correct
28	Correct	5 ms	2424 KB	Output is correct
29	Correct	9 ms	7032 KB	Output is correct
30	Incorrect	9 ms	5752 KB	Output isn't correct
31	Incorrect	7 ms	4344 KB	Output isn't correct
32	Incorrect	8 ms	5624 KB	Output isn't correct
33	Correct	10 ms	7032 KB	Output is correct
34	Correct	5 ms	2680 KB	Output is correct
35	Incorrect	7 ms	3704 KB	Output isn't correct
36	Correct	11 ms	8312 KB	Output is correct
37	Correct	2 ms	632 KB	Output is correct
38	Correct	202 ms	75408 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Incorrect	32 ms	20600 KB	Output isn't correct
41	Correct	2 ms	632 KB	Output is correct
42	Correct	3 ms	1700 KB	Output is correct
43	Correct	328 ms	104124 KB	Output is correct
44	Correct	12 ms	8412 KB	Output is correct
45	Correct	260 ms	89128 KB	Output is correct
46	Correct	206 ms	75256 KB	Output is correct
47	Correct	252 ms	89168 KB	Output is correct
48	Correct	224 ms	79436 KB	Output is correct
49	Correct	201 ms	75388 KB	Output is correct
50	Correct	247 ms	79508 KB	Output is correct
51	Correct	265 ms	79344 KB	Output is correct
52	Correct	251 ms	79336 KB	Output is correct
53	Correct	248 ms	78748 KB	Output is correct
54	Correct	211 ms	63980 KB	Output is correct
55	Correct	197 ms	62192 KB	Output is correct
56	Correct	251 ms	79388 KB	Output is correct
57	Correct	225 ms	56436 KB	Output is correct
58	Correct	206 ms	62328 KB	Output is correct
59	Correct	193 ms	58228 KB	Output is correct
60	Correct	200 ms	67176 KB	Output is correct
61	Correct	201 ms	75000 KB	Output is correct
62	Correct	208 ms	74972 KB	Output is correct
63	Correct	209 ms	74872 KB	Output is correct
64	Correct	202 ms	57852 KB	Output is correct
65	Correct	249 ms	78164 KB	Output is correct
66	Correct	202 ms	70904 KB	Output is correct
67	Correct	216 ms	79080 KB	Output is correct
68	Correct	217 ms	79080 KB	Output is correct
69	Correct	191 ms	55160 KB	Output is correct
70	Incorrect	139 ms	30936 KB	Output isn't correct
71	Incorrect	211 ms	47192 KB	Output isn't correct
72	Correct	215 ms	52040 KB	Output is correct
73	Incorrect	217 ms	52580 KB	Output isn't correct
74	Incorrect	226 ms	55096 KB	Output isn't correct
75	Incorrect	210 ms	56568 KB	Output isn't correct
76	Correct	216 ms	57976 KB	Output is correct
77	Correct	216 ms	58488 KB	Output is correct
78	Correct	218 ms	58624 KB	Output is correct
79	Incorrect	198 ms	31096 KB	Output isn't correct
80	Incorrect	178 ms	32504 KB	Output isn't correct
81	Incorrect	179 ms	32780 KB	Output isn't correct
82	Correct	196 ms	61432 KB	Output is correct
83	Incorrect	193 ms	61524 KB	Output isn't correct
84	Incorrect	168 ms	26488 KB	Output isn't correct
85	Incorrect	196 ms	60508 KB	Output isn't correct
86	Incorrect	199 ms	74000 KB	Output isn't correct
87	Correct	192 ms	59384 KB	Output is correct
88	Incorrect	194 ms	60244 KB	Output isn't correct
89	Incorrect	197 ms	69004 KB	Output isn't correct
90	Incorrect	128 ms	45176 KB	Output isn't correct
91	Correct	195 ms	64244 KB	Output is correct
92	Correct	195 ms	65784 KB	Output is correct
93	Correct	202 ms	72572 KB	Output is correct
94	Incorrect	221 ms	68216 KB	Output isn't correct
95	Incorrect	221 ms	62044 KB	Output isn't correct
96	Incorrect	219 ms	61788 KB	Output isn't correct
97	Correct	215 ms	74380 KB	Output is correct
98	Correct	222 ms	61688 KB	Output is correct
99	Incorrect	198 ms	67860 KB	Output isn't correct
100	Incorrect	219 ms	73084 KB	Output isn't correct