oj.uz

Submission #93224

# Submission time Handle Problem Language Result Execution time Memory
93224 2019-01-07T10:08:21 Z Vardanyan Bomb (IZhO17_bomb) C++14
70 / 100
 328 ms 104124 KB 
#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

# Verdict Execution time Memory 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