CSES - IZhO 2017, day 2 - Results
Submission details
Task:Bomb
Sender:ollpu
Submission time:2019-02-10 15:55:54 +0200
Language:C++
Status:READY
Result:86
Feedback
groupverdictscore
#10
#20
#3ACCEPTED1
#40
#50
#6ACCEPTED1
#70
#8ACCEPTED1
#9ACCEPTED1
#10ACCEPTED1
#11ACCEPTED1
#12ACCEPTED1
#13ACCEPTED1
#14ACCEPTED1
#15ACCEPTED1
#16ACCEPTED1
#17ACCEPTED1
#18ACCEPTED1
#19ACCEPTED1
#20ACCEPTED1
#21ACCEPTED1
#22ACCEPTED1
#23ACCEPTED1
#24ACCEPTED1
#25ACCEPTED1
#260
#270
#28ACCEPTED1
#29ACCEPTED1
#30ACCEPTED1
#31ACCEPTED1
#32ACCEPTED1
#33ACCEPTED1
#34ACCEPTED1
#35ACCEPTED1
#360
#37ACCEPTED1
#38ACCEPTED1
#39ACCEPTED1
#40ACCEPTED1
#41ACCEPTED1
#42ACCEPTED1
#43ACCEPTED1
#44ACCEPTED1
#45ACCEPTED1
#46ACCEPTED1
#47ACCEPTED1
#48ACCEPTED1
#490
#50ACCEPTED1
#51ACCEPTED1
#52ACCEPTED1
#53ACCEPTED1
#54ACCEPTED1
#55ACCEPTED1
#56ACCEPTED1
#57ACCEPTED1
#58ACCEPTED1
#59ACCEPTED1
#600
#610
#620
#630
#640
#65ACCEPTED1
#66ACCEPTED1
#67ACCEPTED1
#68ACCEPTED1
#69ACCEPTED1
#70ACCEPTED1
#71ACCEPTED1
#72ACCEPTED1
#73ACCEPTED1
#74ACCEPTED1
#75ACCEPTED1
#76ACCEPTED1
#77ACCEPTED1
#78ACCEPTED1
#79ACCEPTED1
#80ACCEPTED1
#81ACCEPTED1
#82ACCEPTED1
#83ACCEPTED1
#84ACCEPTED1
#85ACCEPTED1
#86ACCEPTED1
#87ACCEPTED1
#88ACCEPTED1
#89ACCEPTED1
#90ACCEPTED1
#91ACCEPTED1
#92ACCEPTED1
#93ACCEPTED1
#94ACCEPTED1
#95ACCEPTED1
#96ACCEPTED1
#97ACCEPTED1
#98ACCEPTED1
#99ACCEPTED1
#100ACCEPTED1
Test results
testverdicttimegroup
#10.02 s1details
#20.02 s2details
#3ACCEPTED0.07 s3details
#40.07 s4details
#50.04 s5details
#6ACCEPTED0.03 s6details
#70.02 s7details
#8ACCEPTED0.02 s8details
#9ACCEPTED0.02 s9details
#10ACCEPTED0.02 s10details
#11ACCEPTED0.03 s11details
#12ACCEPTED0.01 s12details
#13ACCEPTED0.01 s13details
#14ACCEPTED0.01 s14details
#15ACCEPTED0.02 s15details
#16ACCEPTED0.01 s16details
#17ACCEPTED0.01 s17details
#18ACCEPTED0.01 s18details
#19ACCEPTED0.01 s19details
#20ACCEPTED0.01 s20details
#21ACCEPTED0.02 s21details
#22ACCEPTED0.02 s22details
#23ACCEPTED0.03 s23details
#24ACCEPTED0.02 s24details
#25ACCEPTED0.03 s25details
#260.02 s26details
#270.03 s27details
#28ACCEPTED0.03 s28details
#29ACCEPTED0.06 s29details
#30ACCEPTED0.05 s30details
#31ACCEPTED0.04 s31details
#32ACCEPTED0.04 s32details
#33ACCEPTED0.04 s33details
#34ACCEPTED0.04 s34details
#35ACCEPTED0.05 s35details
#360.05 s36details
#37ACCEPTED0.02 s37details
#38ACCEPTED0.72 s38details
#39ACCEPTED0.02 s39details
#40ACCEPTED0.10 s40details
#41ACCEPTED0.02 s41details
#42ACCEPTED0.02 s42details
#43ACCEPTED0.74 s43details
#44ACCEPTED0.06 s44details
#45ACCEPTED0.70 s45details
#46ACCEPTED0.69 s46details
#47ACCEPTED0.71 s47details
#48ACCEPTED0.69 s48details
#490.73 s49details
#50ACCEPTED0.70 s50details
#51ACCEPTED0.70 s51details
#52ACCEPTED0.70 s52details
#53ACCEPTED0.69 s53details
#54ACCEPTED0.68 s54details
#55ACCEPTED0.69 s55details
#56ACCEPTED0.73 s56details
#57ACCEPTED0.68 s57details
#58ACCEPTED0.68 s58details
#59ACCEPTED0.67 s59details
#600.69 s60details
#610.71 s61details
#620.72 s62details
#630.72 s63details
#640.68 s64details
#65ACCEPTED0.69 s65details
#66ACCEPTED0.69 s66details
#67ACCEPTED0.69 s67details
#68ACCEPTED0.70 s68details
#69ACCEPTED0.67 s69details
#70ACCEPTED0.43 s70details
#71ACCEPTED0.68 s71details
#72ACCEPTED0.68 s72details
#73ACCEPTED0.68 s73details
#74ACCEPTED0.67 s74details
#75ACCEPTED0.67 s75details
#76ACCEPTED0.67 s76details
#77ACCEPTED0.68 s77details
#78ACCEPTED0.68 s78details
#79ACCEPTED0.66 s79details
#80ACCEPTED0.66 s80details
#81ACCEPTED0.68 s81details
#82ACCEPTED0.69 s82details
#83ACCEPTED0.69 s83details
#84ACCEPTED0.66 s84details
#85ACCEPTED0.68 s85details
#86ACCEPTED0.71 s86details
#87ACCEPTED0.67 s87details
#88ACCEPTED0.68 s88details
#89ACCEPTED0.68 s89details
#90ACCEPTED0.44 s90details
#91ACCEPTED0.68 s91details
#92ACCEPTED0.68 s92details
#93ACCEPTED0.71 s93details
#94ACCEPTED0.71 s94details
#95ACCEPTED0.68 s95details
#96ACCEPTED0.69 s96details
#97ACCEPTED0.71 s97details
#98ACCEPTED0.68 s98details
#99ACCEPTED0.68 s99details
#100ACCEPTED0.71 s100details

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int ot[2500][2500], rt[2500][2500], st[4][2500];
int d[2500], ps[2500], ns[2500];
vector<pair<int, int>> sk(2501);
void c(int n, int m, int *cst) {
  int hcap = n;
  for (int i = 0; i < n; ++i) cst[i] = m;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (!i || !rt[i][j]) d[j] = 0;
      d[j] += rt[i][j];
    }
    sk.clear();
    sk.emplace_back(-1, -1);
    for (int j = 0; j < m; ++j) {
      while (sk.back().F >= d[j]) sk.pop_back();
      ps[j] = sk.back().S;
      sk.emplace_back(d[j], j);
    }
    sk.clear();
    sk.emplace_back(-1, m);
    for (int j = m-1; j >= 0; --j) {
      while (sk.back().F >= d[j]) sk.pop_back();
      ns[j] = sk.back().S;
      sk.emplace_back(d[j], j);
    }
    for (int j = 0; j < n; ++j) {
      if (!rt[i][j] || (i < n-1 && rt[i+1][j])) continue;
      hcap = d[j];
      int psi = j, psd = d[j], nsi = j, nsd = d[j];
      for (int ah = d[j]-1; ah >= 0; --ah) {
        while (psd > ah) {
          psi = ps[psi];
          if (psi == -1) psd = -1;
          else psd = d[psi];
        }
        while (nsd > ah) {
          nsi = ns[nsi];
          if (nsi == m) nsd = -1;
          else nsd = d[nsi];
        }
        cst[ah] = min(cst[ah], nsi-psi-1);
      }
    }
  }
  for (int i = hcap; i < n; ++i) cst[i] = 0;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> ws;
    for (int j = 0; j < m; ++j) {
      char c;
      cin >> c;
      ot[i][j] = c == '1';
      rt[i][j] = ot[i][j];
    }
  }
  c(n, m, st[0]);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      rt[j][i] = ot[i][j];
    }
  }
  c(m, n, st[1]);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      rt[n-i-1][j] = ot[i][j];
    }
  }
  c(n, m, st[2]);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      rt[m-j-1][i] = ot[i][j];
    }
  }
  c(m, n, st[3]);
  long res = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (j+1 > st[0][i]) continue;
      if (i+1 > st[1][j]) continue;
      if (j+1 > st[2][i]) continue;
      if (i+1 > st[3][j]) continue;
      res = max(res, long(i+1)*(j+1));
    }
  }
  cout << res << endl;
}

Test details

Test 1

Group: 1

Verdict:

input
1 20
00001111101110011110

correct output
3

user output
4

Test 2

Group: 2

Verdict:

input
20 1
1
1
1
0
...

correct output
2

user output
3

Test 3

Group: 3

Verdict: ACCEPTED

input
2499 1
1
1
1
1
...

correct output
38

user output
38

Test 4

Group: 4

Verdict:

input
2499 1
1
1
1
1
...

correct output
55

user output
283

Test 5

Group: 5

Verdict:

input
1 2500
111111111110111111111110111111...

correct output
7

user output
11

Test 6

Group: 6

Verdict: ACCEPTED

input
1 1000
111111111111111111111111111111...

correct output
33

user output
33

Test 7

Group: 7

Verdict:

input
5 5
11111
11111
11011
11111
...

correct output
4

user output
10

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:

input
100 100
111111111111111111111111111111...

correct output
132

user output
440

Test 27

Group: 27

Verdict:

input
295 268
111111111111111111111111111111...

correct output
3

user output
20

Test 28

Group: 28

Verdict: ACCEPTED

input
290 383
111111110000000000000000000000...

correct output
20

user output
20

Test 29

Group: 29

Verdict: ACCEPTED

input
390 320
000000000000000000000000000000...

correct output
3038

user output
3038

Test 30

Group: 30

Verdict: ACCEPTED

input
432 434
111111111111111111111111111111...

correct output
221

user output
221

Test 31

Group: 31

Verdict: ACCEPTED

input
334 450
111111111111111111111111111111...

correct output
391

user output
391

Test 32

Group: 32

Verdict: ACCEPTED

input
407 383
111111111111111111111111111111...

correct output
156

user output
156

Test 33

Group: 33

Verdict: ACCEPTED

input
450 450
111111111111111111111111111111...

correct output
1235

user output
1235

Test 34

Group: 34

Verdict: ACCEPTED

input
356 231
000000000001111111111110000000...

correct output
42

user output
42

Test 35

Group: 35

Verdict: ACCEPTED

input
450 450
111111111111111111111111111111...

correct output
192

user output
192

Test 36

Group: 36

Verdict:

input
450 450
111111111111111111111111111111...

correct output
1404

user output
6210

Test 37

Group: 37

Verdict: ACCEPTED

input
20 20
00000000001111111111
00000000001111111111
00000000001111111111
00000000001111111111
...

correct output
14

user output
14

Test 38

Group: 38

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
6250000

user output
6250000

Test 39

Group: 39

Verdict: ACCEPTED

input
20 20
00000000001111111111
00000000001111111111
00000000111111111111
00000001111111111111
...

correct output
24

user output
24

Test 40

Group: 40

Verdict: ACCEPTED

input
875 882
111111111111111111111111111111...

correct output
69552

user output
69552

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: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
250500

user output
250500

Test 44

Group: 44

Verdict: ACCEPTED

input
450 450
000000000000000000000000000000...

correct output
12864

user output
12864

Test 45

Group: 45

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
399456

user output
399456

Test 46

Group: 46

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111100000...

correct output
625

user output
625

Test 47

Group: 47

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
395486

user output
395486

Test 48

Group: 48

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
3360

user output
3360

Test 49

Group: 49

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
28

user output
2482

Test 50

Group: 50

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
7348

user output
7348

Test 51

Group: 51

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
6622

user output
6622

Test 52

Group: 52

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
5593

user output
5593

Test 53

Group: 53

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
4545

user output
4545

Test 54

Group: 54

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
4067

user output
4067

Test 55

Group: 55

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
2806

user output
2806

Test 56

Group: 56

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
122500

user output
122500

Test 57

Group: 57

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
4674

user output
4674

Test 58

Group: 58

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
6272

user output
6272

Test 59

Group: 59

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
3337

user output
3337

Test 60

Group: 60

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
870

user output
899

Test 61

Group: 61

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
532

user output
70000

Test 62

Group: 62

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
114271

user output
1247500

Test 63

Group: 63

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
1560001

user output
3122500

Test 64

Group: 64

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
62500

user output
625000

Test 65

Group: 65

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
1400

user output
1400

Test 66

Group: 66

Verdict: ACCEPTED

input
2500 2500
000000111111111111111111111111...

correct output
9910

user output
9910

Test 67

Group: 67

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
9879

user output
9879

Test 68

Group: 68

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
16224

user output
16224

Test 69

Group: 69

Verdict: ACCEPTED

input
2500 2500
000000000000000000000000000000...

correct output
6300

user output
6300

Test 70

Group: 70

Verdict: ACCEPTED

input
2000 2000
111111111111111111111111111111...

correct output
59760

user output
59760

Test 71

Group: 71

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
40480

user output
40480

Test 72

Group: 72

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
137159

user output
137159

Test 73

Group: 73

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
32110

user output
32110

Test 74

Group: 74

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
10914

user output
10914

Test 75

Group: 75

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
124074

user output
124074

Test 76

Group: 76

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
4617

user output
4617

Test 77

Group: 77

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
106981

user output
106981

Test 78

Group: 78

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
44980

user output
44980

Test 79

Group: 79

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111110000...

correct output
1365

user output
1365

Test 80

Group: 80

Verdict: ACCEPTED

input
2500 2500
111111111111111111110000000000...

correct output
602

user output
602

Test 81

Group: 81

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
2709

user output
2709

Test 82

Group: 82

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
149556

user output
149556

Test 83

Group: 83

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
11289

user output
11289

Test 84

Group: 84

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
366

user output
366

Test 85

Group: 85

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
4814

user output
4814

Test 86

Group: 86

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
132

user output
132

Test 87

Group: 87

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
589

user output
589

Test 88

Group: 88

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
56448

user output
56448

Test 89

Group: 89

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
10044

user output
10044

Test 90

Group: 90

Verdict: ACCEPTED

input
2000 2000
111111111111111111111111111111...

correct output
6384

user output
6384

Test 91

Group: 91

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
15330

user output
15330

Test 92

Group: 92

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
47759

user output
47759

Test 93

Group: 93

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
624

user output
624

Test 94

Group: 94

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
16695

user output
16695

Test 95

Group: 95

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
19224

user output
19224

Test 96

Group: 96

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
89386

user output
89386

Test 97

Group: 97

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
243

user output
243

Test 98

Group: 98

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
73840

user output
73840

Test 99

Group: 99

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
10764

user output
10764

Test 100

Group: 100

Verdict: ACCEPTED

input
2500 2500
111111111111111111111111111111...

correct output
135

user output
135