CSES - IZhO 2017, day 2 - Results
Submission details
Task:Bomb
Sender:Olli
Submission time:2019-02-10 16:21:59 +0200
Language:C++
Status:READY
Result:30
Feedback
groupverdictscore
#1ACCEPTED1
#2ACCEPTED1
#3ACCEPTED1
#4ACCEPTED1
#50
#60
#7ACCEPTED1
#8ACCEPTED1
#9ACCEPTED1
#10ACCEPTED1
#11ACCEPTED1
#12ACCEPTED1
#13ACCEPTED1
#14ACCEPTED1
#15ACCEPTED1
#16ACCEPTED1
#17ACCEPTED1
#18ACCEPTED1
#19ACCEPTED1
#20ACCEPTED1
#21ACCEPTED1
#22ACCEPTED1
#23ACCEPTED1
#24ACCEPTED1
#25ACCEPTED1
#26ACCEPTED1
#270
#28ACCEPTED1
#290
#300
#310
#320
#330
#34ACCEPTED1
#350
#360
#37ACCEPTED1
#380
#39ACCEPTED1
#400
#41ACCEPTED1
#42ACCEPTED1
#430
#440
#450
#460
#470
#480
#490
#500
#510
#520
#530
#540
#550
#560
#570
#580
#590
#600
#610
#620
#630
#640
#650
#660
#670
#680
#690
#700
#710
#720
#730
#740
#750
#760
#770
#780
#790
#800
#810
#820
#830
#840
#850
#860
#870
#880
#890
#900
#910
#920
#930
#940
#950
#960
#970
#980
#990
#1000
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.02 s2details
#3ACCEPTED0.06 s3details
#4ACCEPTED0.06 s4details
#50.38 s5details
#60.09 s6details
#7ACCEPTED0.02 s7details
#8ACCEPTED0.01 s8details
#9ACCEPTED0.02 s9details
#10ACCEPTED0.02 s10details
#11ACCEPTED0.01 s11details
#12ACCEPTED0.02 s12details
#13ACCEPTED0.01 s13details
#14ACCEPTED0.03 s14details
#15ACCEPTED0.02 s15details
#16ACCEPTED0.01 s16details
#17ACCEPTED0.04 s17details
#18ACCEPTED0.02 s18details
#19ACCEPTED0.03 s19details
#20ACCEPTED0.04 s20details
#21ACCEPTED0.03 s21details
#22ACCEPTED0.04 s22details
#23ACCEPTED0.05 s23details
#24ACCEPTED0.04 s24details
#25ACCEPTED0.05 s25details
#26ACCEPTED0.14 s26details
#27--27details
#28ACCEPTED0.62 s28details
#29--29details
#30--30details
#31--31details
#32--32details
#33--33details
#34ACCEPTED0.32 s34details
#35--35details
#36--36details
#37ACCEPTED0.01 s37details
#38--38details
#39ACCEPTED0.03 s39details
#40--40details
#41ACCEPTED0.02 s41details
#42ACCEPTED0.09 s42details
#43--43details
#44--44details
#45--45details
#46--46details
#47--47details
#48--48details
#49--49details
#50--50details
#51--51details
#52--52details
#53--53details
#54--54details
#55--55details
#56--56details
#57--57details
#58--58details
#59--59details
#60--60details
#61--61details
#62--62details
#63--63details
#64--64details
#65--65details
#66--66details
#67--67details
#68--68details
#69--69details
#70--70details
#71--71details
#72--72details
#73--73details
#74--74details
#75--75details
#76--76details
#77--77details
#78--78details
#79--79details
#80--80details
#81--81details
#82--82details
#83--83details
#84--84details
#85--85details
#86--86details
#87--87details
#88--88details
#89--89details
#90--90details
#91--91details
#92--92details
#93--93details
#94--94details
#95--95details
#96--96details
#97--97details
#98--98details
#99--99details
#100--100details

Code

#include <iostream>

using namespace std;

const int N = 2525;
const int M = 512;

bool map[N][N];

int u[N][N];
int d[N][N];

int ut[N][2*M];
int dt[N][2*M];


int mini(int y, int a, int b) {
	a += M-1; b+= M-1;
	int miU = 1e9;
	int miD = 1e9;
	while(a <= b) {
		if(a%2 == 1) {
			miU = min(miU, ut[y][a]);
			miD = min(miD, dt[y][a]);
			++a;
		}
		if(b%2 == 0) {
			miU = min(miU, ut[y][b]);
			miD = min(miD, dt[y][b]);
			--b;
		}
		a/=2; b/=2;
	}
	return miU + miD - 1;
}

int lat[N][N];

int main() {
	int h, w;
	cin >> h >> w;
	for(int hh = 1; hh <= h; ++hh) {
		for(int ww = 1; ww <= w; ++ww) {
			char a;
			cin >> a;
			if(a == '1') {
				map[hh][ww] = true;
			}
		}
	}


	for(int y = 1; y <= h; ++y) {
		for(int x = 1; x <= w; ++x) {
			if(!map[y][x]) {
				u[y][x] = 0;
			} else {
				u[y][x] = u[y-1][x] + 1;
			}
		}
	}

	for(int y = h; y >= 1; --y) {
		for(int x = 1; x <= w; ++x) {
			if(!map[y][x]) {
				d[y][x] = 0;
			} else {
				d[y][x] = d[y+1][x] + 1;
			}
		}
	}

/*
	for(int y = 1; y <= h; ++y) {
		for(int x = 1; x <= w; ++x) {
			cout << d[y][x] << " ";
		}
		cout << "\n";
	}
*/
	for(int y = 1; y <= h; ++y) {
		for(int x = 1; x <= w; ++x) {
			ut[y][x-1+M] = u[y][x];
			dt[y][x-1+M] = d[y][x];
		}

		for(int i = M-1; i >= 1; --i) {
			ut[y][i] = min(ut[y][2*i], ut[y][2*i+1]);
			dt[y][i] = min(dt[y][2*i], dt[y][2*i+1]);
		}
	}


	int ans = 0;
	int co = 1;
	for(int ww = 1; ww <= w; ++ww) {
		int maxH = 0;
		for(int b = 12; b >= 0; --b) {
			int newH = maxH + (1<<b);
			if(newH > h) continue;

			for(int y = 1; y <= h; ++y) {
				for(int x = 1; x <= w-ww+1; ++x) {
					if(!map[y][x]) continue;
//					if(lat[y][x] == co) continue;
					if(mini(y, x, x+ww-1) >= newH) {
						for(int xx = x; xx <= x + ww - 1; ++xx) {
							lat[y][xx] = co;
						}
					}
				}
			}
			bool wo = true;
			for(int y = 1; y <= h; ++y) {
				for(int x = 1; x <= w; ++x) {
					if(map[y][x] && lat[y][x] != co) {
						wo = false;
						break;
					}
				}
			}
			++co;
			if(wo) {
				maxH = newH;
			}
		}
		ans = max(maxH*ww, ans);
	}

	cout << ans << "\n";
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1 20
00001111101110011110

correct output
3

user output
3

Test 2

Group: 2

Verdict: ACCEPTED

input
20 1
1
1
1
0
...

correct output
2

user output
2

Test 3

Group: 3

Verdict: ACCEPTED

input
2499 1
1
1
1
1
...

correct output
38

user output
38

Test 4

Group: 4

Verdict: ACCEPTED

input
2499 1
1
1
1
1
...

correct output
55

user output
55

Test 5

Group: 5

Verdict:

input
1 2500
111111111110111111111110111111...

correct output
7

user output
11

Test 6

Group: 6

Verdict:

input
1 1000
111111111111111111111111111111...

correct output
33

user output
85

Test 7

Group: 7

Verdict: ACCEPTED

input
5 5
11111
11111
11011
11111
...

correct output
4

user output
4

Test 8

Group: 8

Verdict: ACCEPTED

input
20 20
11111000000000000000
11111000000000000000
11111100000000000000
11111111111000000000
...

correct output
8

user output
8

Test 9

Group: 9

Verdict: ACCEPTED

input
20 20
11111100000000000000
11111100000000000000
11111110000000000000
11111111111110000000
...

correct output
12

user output
12

Test 10

Group: 10

Verdict: ACCEPTED

input
14 13
0000011100000
0000011100000
0000011100000
0000011110000
...

correct output
4

user output
4

Test 11

Group: 11

Verdict: ACCEPTED

input
20 19
1111110000000000000
1111111000000000000
1111111000000000000
1111111000000000000
...

correct output
10

user output
10

Test 12

Group: 12

Verdict: ACCEPTED

input
15 15
110000000000000
110000000000000
110000000000000
111000000000000
...

correct output
2

user output
2

Test 13

Group: 13

Verdict: ACCEPTED

input
15 11
00111000000
00111000000
00111000000
00111000000
...

correct output
3

user output
3

Test 14

Group: 14

Verdict: ACCEPTED

input
16 16
0000111100001111
0000111100001111
0000111100001111
0000111100001111
...

correct output
16

user output
16

Test 15

Group: 15

Verdict: ACCEPTED

input
18 18
111110000000000000
111110000000000000
111110000000000000
111111000000000000
...

correct output
8

user output
8

Test 16

Group: 16

Verdict: ACCEPTED

input
20 20
11111111111111011111
11111111111111011111
11111111111111011111
11111111111111111111
...

correct output
20

user output
20

Test 17

Group: 17

Verdict: ACCEPTED

input
65 70
000000000000000011111000000000...

correct output
15

user output
15

Test 18

Group: 18

Verdict: ACCEPTED

input
70 62
111100000000000000000000000000...

correct output
6

user output
6

Test 19

Group: 19

Verdict: ACCEPTED

input
94 78
111111111111111100000000000000...

correct output
22

user output
22

Test 20

Group: 20

Verdict: ACCEPTED

input
92 84
111111111111111110000000000000...

correct output
27

user output
27

Test 21

Group: 21

Verdict: ACCEPTED

input
53 89
000001111000000000000000000000...

correct output
6

user output
6

Test 22

Group: 22

Verdict: ACCEPTED

input
76 93
000011111100000000000000000000...

correct output
12

user output
12

Test 23

Group: 23

Verdict: ACCEPTED

input
100 100
111111111111111111111111111111...

correct output
209

user output
209

Test 24

Group: 24

Verdict: ACCEPTED

input
81 74
111111111111111110000000000000...

correct output
30

user output
30

Test 25

Group: 25

Verdict: ACCEPTED

input
100 100
111111111111111111111111111111...

correct output
80

user output
80

Test 26

Group: 26

Verdict: ACCEPTED

input
100 100
111111111111111111111111111111...

correct output
132

user output
132

Test 27

Group: 27

Verdict:

input
295 268
111111111111111111111111111111...

correct output
3

user output
(empty)

Test 28

Group: 28

Verdict: ACCEPTED

input
290 383
111111110000000000000000000000...

correct output
20

user output
20

Test 29

Group: 29

Verdict:

input
390 320
000000000000000000000000000000...

correct output
3038

user output
(empty)

Test 30

Group: 30

Verdict:

input
432 434
111111111111111111111111111111...

correct output
221

user output
(empty)

Test 31

Group: 31

Verdict:

input
334 450
111111111111111111111111111111...

correct output
391

user output
(empty)

Test 32

Group: 32

Verdict:

input
407 383
111111111111111111111111111111...

correct output
156

user output
(empty)

Test 33

Group: 33

Verdict:

input
450 450
111111111111111111111111111111...

correct output
1235

user output
(empty)

Test 34

Group: 34

Verdict: ACCEPTED

input
356 231
000000000001111111111110000000...

correct output
42

user output
42

Test 35

Group: 35

Verdict:

input
450 450
111111111111111111111111111111...

correct output
192

user output
(empty)

Test 36

Group: 36

Verdict:

input
450 450
111111111111111111111111111111...

correct output
1404

user output
(empty)

Test 37

Group: 37

Verdict: ACCEPTED

input
20 20
00000000001111111111
00000000001111111111
00000000001111111111
00000000001111111111
...

correct output
14

user output
14

Test 38

Group: 38

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
6250000

user output
(empty)

Test 39

Group: 39

Verdict: ACCEPTED

input
20 20
00000000001111111111
00000000001111111111
00000000111111111111
00000001111111111111
...

correct output
24

user output
24

Test 40

Group: 40

Verdict:

input
875 882
111111111111111111111111111111...

correct output
69552

user output
(empty)

Test 41

Group: 41

Verdict: ACCEPTED

input
20 20
00000000111111111111
00000011111111111111
00000011111111111111
00000111111111111111
...

correct output
36

user output
36

Test 42

Group: 42

Verdict: ACCEPTED

input
100 100
000000000000000000000000000000...

correct output
651

user output
651

Test 43

Group: 43

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
250500

user output
(empty)

Test 44

Group: 44

Verdict:

input
450 450
000000000000000000000000000000...

correct output
12864

user output
(empty)

Test 45

Group: 45

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
399456

user output
(empty)

Test 46

Group: 46

Verdict:

input
2500 2500
111111111111111111111111100000...

correct output
625

user output
(empty)

Test 47

Group: 47

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
395486

user output
(empty)

Test 48

Group: 48

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
3360

user output
(empty)

Test 49

Group: 49

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
28

user output
(empty)

Test 50

Group: 50

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
7348

user output
(empty)

Test 51

Group: 51

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
6622

user output
(empty)

Test 52

Group: 52

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
5593

user output
(empty)

Test 53

Group: 53

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
4545

user output
(empty)

Test 54

Group: 54

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
4067

user output
(empty)

Test 55

Group: 55

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
2806

user output
(empty)

Test 56

Group: 56

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
122500

user output
(empty)

Test 57

Group: 57

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
4674

user output
(empty)

Test 58

Group: 58

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
6272

user output
(empty)

Test 59

Group: 59

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
3337

user output
(empty)

Test 60

Group: 60

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
870

user output
(empty)

Test 61

Group: 61

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
532

user output
(empty)

Test 62

Group: 62

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
114271

user output
(empty)

Test 63

Group: 63

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
1560001

user output
(empty)

Test 64

Group: 64

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
62500

user output
(empty)

Test 65

Group: 65

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
1400

user output
(empty)

Test 66

Group: 66

Verdict:

input
2500 2500
000000111111111111111111111111...

correct output
9910

user output
(empty)

Test 67

Group: 67

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
9879

user output
(empty)

Test 68

Group: 68

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
16224

user output
(empty)

Test 69

Group: 69

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
6300

user output
(empty)

Test 70

Group: 70

Verdict:

input
2000 2000
111111111111111111111111111111...

correct output
59760

user output
(empty)

Test 71

Group: 71

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
40480

user output
(empty)

Test 72

Group: 72

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
137159

user output
(empty)

Test 73

Group: 73

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
32110

user output
(empty)

Test 74

Group: 74

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
10914

user output
(empty)

Test 75

Group: 75

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
124074

user output
(empty)

Test 76

Group: 76

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
4617

user output
(empty)

Test 77

Group: 77

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
106981

user output
(empty)

Test 78

Group: 78

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
44980

user output
(empty)

Test 79

Group: 79

Verdict:

input
2500 2500
111111111111111111111111110000...

correct output
1365

user output
(empty)

Test 80

Group: 80

Verdict:

input
2500 2500
111111111111111111110000000000...

correct output
602

user output
(empty)

Test 81

Group: 81

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
2709

user output
(empty)

Test 82

Group: 82

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
149556

user output
(empty)

Test 83

Group: 83

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
11289

user output
(empty)

Test 84

Group: 84

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
366

user output
(empty)

Test 85

Group: 85

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
4814

user output
(empty)

Test 86

Group: 86

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
132

user output
(empty)

Test 87

Group: 87

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
589

user output
(empty)

Test 88

Group: 88

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
56448

user output
(empty)

Test 89

Group: 89

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
10044

user output
(empty)

Test 90

Group: 90

Verdict:

input
2000 2000
111111111111111111111111111111...

correct output
6384

user output
(empty)

Test 91

Group: 91

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
15330

user output
(empty)

Test 92

Group: 92

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
47759

user output
(empty)

Test 93

Group: 93

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
624

user output
(empty)

Test 94

Group: 94

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
16695

user output
(empty)

Test 95

Group: 95

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
19224

user output
(empty)

Test 96

Group: 96

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
89386

user output
(empty)

Test 97

Group: 97

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
243

user output
(empty)

Test 98

Group: 98

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
73840

user output
(empty)

Test 99

Group: 99

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
10764

user output
(empty)

Test 100

Group: 100

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
135

user output
(empty)