답안 #93216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93216	2019-01-07T09:50:42 Z	Vardanyan	Bomb (IZhO17_bomb)	C++14	70 / 100	336 ms	104112 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;
void calc1(int i, int j,int pl){
	int now = -1;
	for (int ii = i; ii <= n; ii+=pl){
		if (now == -1 || ajic[ii][j] < now){
			now = ajic[ii][j];
		}
		now = min(now, mnw);
	if(pl == 1)	v.push_back({ ii - i + 1, now });
	else v.push_back({ i - ii + 1, now });
	}
}
void calc2(int i, int j,int pl){

}
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 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;
		}
	}
	long long ans = 0;
	for (int i = 0; i < v.size(); i++){
		long long a = v[i].first;
		if (a > mnh) continue;
		long long b = M[a];
		a *= b;
		ans = max(ans, a);
	}
	cout << ans << endl;
	return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:51:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(now) mnw = min(mnw, now);
    ^~
bomb.cpp:52:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     now = 0;
     ^~~
bomb.cpp:72:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(now) mnh = min(mnh, now);
    ^~
bomb.cpp:73:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     now = 0;
     ^~~
bomb.cpp:137:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
bomb.cpp:146: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	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	72 ms	47056 KB	Output is correct
4	Correct	47 ms	38752 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	508 KB	Output is correct
9	Incorrect	2 ms	632 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	504 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	1272 KB	Output is correct
18	Correct	2 ms	888 KB	Output is correct
19	Incorrect	3 ms	1272 KB	Output isn't correct
20	Correct	3 ms	1276 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	3 ms	1528 KB	Output is correct
26	Correct	3 ms	1656 KB	Output is correct
27	Correct	6 ms	4984 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	5880 KB	Output isn't correct
31	Incorrect	8 ms	4344 KB	Output isn't correct
32	Incorrect	8 ms	5496 KB	Output isn't correct
33	Correct	10 ms	6904 KB	Output is correct
34	Correct	5 ms	2680 KB	Output is correct
35	Incorrect	8 ms	3704 KB	Output isn't correct
36	Correct	10 ms	8312 KB	Output is correct
37	Correct	2 ms	632 KB	Output is correct
38	Correct	206 ms	75228 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Incorrect	31 ms	20472 KB	Output isn't correct
41	Correct	2 ms	632 KB	Output is correct
42	Correct	3 ms	1656 KB	Output is correct
43	Correct	316 ms	104112 KB	Output is correct
44	Correct	12 ms	8440 KB	Output is correct
45	Correct	254 ms	89040 KB	Output is correct
46	Correct	211 ms	75256 KB	Output is correct
47	Correct	253 ms	89192 KB	Output is correct
48	Correct	217 ms	79376 KB	Output is correct
49	Correct	209 ms	75128 KB	Output is correct
50	Correct	221 ms	79208 KB	Output is correct
51	Correct	237 ms	79244 KB	Output is correct
52	Correct	220 ms	79160 KB	Output is correct
53	Correct	221 ms	78684 KB	Output is correct
54	Correct	227 ms	63896 KB	Output is correct
55	Correct	202 ms	62028 KB	Output is correct
56	Correct	226 ms	79232 KB	Output is correct
57	Correct	221 ms	56260 KB	Output is correct
58	Correct	200 ms	62184 KB	Output is correct
59	Correct	219 ms	58208 KB	Output is correct
60	Correct	216 ms	66936 KB	Output is correct
61	Correct	220 ms	75128 KB	Output is correct
62	Correct	220 ms	75152 KB	Output is correct
63	Correct	217 ms	75128 KB	Output is correct
64	Correct	214 ms	58004 KB	Output is correct
65	Correct	243 ms	78188 KB	Output is correct
66	Correct	228 ms	70492 KB	Output is correct
67	Correct	237 ms	78856 KB	Output is correct
68	Correct	239 ms	78824 KB	Output is correct
69	Correct	211 ms	54776 KB	Output is correct
70	Incorrect	131 ms	30584 KB	Output isn't correct
71	Incorrect	218 ms	46892 KB	Output isn't correct
72	Correct	208 ms	52088 KB	Output is correct
73	Incorrect	211 ms	52600 KB	Output isn't correct
74	Incorrect	223 ms	54776 KB	Output isn't correct
75	Incorrect	219 ms	56248 KB	Output isn't correct
76	Correct	215 ms	57684 KB	Output is correct
77	Correct	222 ms	58076 KB	Output is correct
78	Correct	216 ms	58360 KB	Output is correct
79	Incorrect	198 ms	30712 KB	Output isn't correct
80	Incorrect	170 ms	32076 KB	Output isn't correct
81	Incorrect	179 ms	32568 KB	Output isn't correct
82	Correct	221 ms	60896 KB	Output is correct
83	Incorrect	217 ms	61084 KB	Output isn't correct
84	Incorrect	196 ms	25976 KB	Output isn't correct
85	Incorrect	218 ms	60036 KB	Output isn't correct
86	Incorrect	223 ms	73540 KB	Output isn't correct
87	Correct	222 ms	59052 KB	Output is correct
88	Incorrect	215 ms	59788 KB	Output isn't correct
89	Incorrect	219 ms	68452 KB	Output isn't correct
90	Incorrect	147 ms	44884 KB	Output isn't correct
91	Correct	221 ms	63760 KB	Output is correct
92	Correct	221 ms	65400 KB	Output is correct
93	Correct	216 ms	72528 KB	Output is correct
94	Incorrect	223 ms	67200 KB	Output isn't correct
95	Incorrect	215 ms	61048 KB	Output isn't correct
96	Incorrect	215 ms	60664 KB	Output isn't correct
97	Correct	221 ms	73336 KB	Output is correct
98	Correct	219 ms	60684 KB	Output is correct
99	Incorrect	336 ms	66724 KB	Output isn't correct
100	Incorrect	208 ms	72184 KB	Output isn't correct