CSES - IZhO 2017, day 2 - Results
Submission details
Task:Bomb
Sender:Yytsi
Submission time:2019-02-11 10:00:37 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
#70
#80
#90
#100
#110
#120
#130
#140
#150
#160
#170
#180
#190
#200
#210
#220
#230
#240
#250
#260
#270
#280
#290
#300
#310
#320
#330
#340
#350
#360
#370
#380
#390
#400
#410
#420
#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
#10.02 s1details
#20.02 s2details
#30.03 s3details
#40.03 s4details
#50.02 s5details
#60.01 s6details
#70.02 s7details
#80.02 s8details
#90.01 s9details
#100.01 s10details
#110.02 s11details
#120.02 s12details
#130.01 s13details
#140.02 s14details
#150.02 s15details
#160.03 s16details
#170.02 s17details
#180.01 s18details
#190.02 s19details
#200.01 s20details
#210.03 s21details
#220.02 s22details
#230.02 s23details
#240.02 s24details
#250.02 s25details
#260.02 s26details
#270.02 s27details
#280.02 s28details
#290.02 s29details
#300.02 s30details
#310.03 s31details
#320.03 s32details
#330.03 s33details
#340.02 s34details
#350.03 s35details
#360.03 s36details
#370.02 s37details
#380.33 s38details
#390.03 s39details
#400.05 s40details
#410.02 s41details
#420.02 s42details
#430.29 s43details
#440.03 s44details
#450.29 s45details
#460.27 s46details
#470.28 s47details
#480.28 s48details
#490.33 s49details
#500.29 s50details
#510.28 s51details
#520.28 s52details
#530.28 s53details
#540.23 s54details
#550.23 s55details
#560.33 s56details
#570.22 s57details
#580.23 s58details
#590.22 s59details
#600.27 s60details
#610.33 s61details
#620.33 s62details
#630.34 s63details
#640.23 s64details
#650.28 s65details
#660.27 s66details
#670.28 s67details
#680.29 s68details
#690.22 s69details
#700.12 s70details
#710.20 s71details
#720.21 s72details
#730.23 s73details
#740.22 s74details
#750.23 s75details
#760.23 s76details
#770.24 s77details
#780.23 s78details
#790.16 s79details
#800.15 s80details
#810.18 s81details
#820.23 s82details
#830.24 s83details
#840.16 s84details
#850.23 s85details
#860.32 s86details
#870.23 s87details
#880.24 s88details
#890.27 s89details
#900.15 s90details
#910.24 s91details
#920.26 s92details
#930.32 s93details
#940.27 s94details
#950.24 s95details
#960.24 s96details
#970.32 s97details
#980.23 s98details
#990.26 s99details
#1000.31 s100details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:101:19: warning: operation on 'idx' may be undefined [-Wsequence-point]
         mx_height[++idx] = min(mx_height[idx], u+d-1);
                   ^~~~~
input/code.cpp:114:19: warning: operation on 'idx' may be undefined [-Wsequence-point]
         mx_height[++idx] = min(mx_height[idx], u+d-1);
                   ^~~~~

Code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 2505
bool A[N][N];
int dp[N][N];
int up[N][N], down[N][N];
int mx_height[N];

int n, m;

int scanline(int y) {
  // Scan minimum constraint for width.
  int mn = 1e9;
  int c = 0;
  FOR(x,1,m+1) {
    if (A[y][x]) {
      c++;
    } else {
      if (c == 0) continue;
      mn = min(mn, c);
      c = 0;
    }
  }

  if (c != 0) mn = min(c, mn);

  return mn;
}

int scancol(int x) {
  // Scan minimum constraint for height.
  int mn = 1e9;
  int c = 0;
  FOR(y,1,n+1) {
    if (A[y][x]) {
      c++;
    } else {
      if (c == 0) continue;
      mn = min(mn, c);
      c = 0;
    }
  }

  if (c != 0) mn = min(c, mn);

  return mn;
}



int main() {
  IO; cin>>n>>m;
  FOR(y,1,n+1) {
    FOR(x,1,m+1) {
      char c; cin>>c;
      if (c == '1') A[y][x] = true;
    }
  }

  int H = n, W = m;
  FOR(y,1,n+1) {
    int r = scanline(y);
    if (r == 1e9) continue;
    W = min(W, r);
  }

  FOR(x,1,m+1) {
    int r = scancol(x);
    if (r == 1e9) continue;
    H = min(H, r);
  }

  FOR(x,1,m+1) {
    for (int y = n; y >= 1; y--) {
      if (A[y][x]) down[y][x] = down[y+1][x] + 1;
    }

    FOR(y,1,n+1) {
      if (A[y][x]) up[y][x] = up[y-1][x] + 1;
    }
  }

  FOR(w,1,W+1) mx_height[w] = H;
  FOR(y,1,n+1) {
    int idx = 0, u = 1e9, d = 1e9;

    FOR(x,1,m+1) {
      if (A[y][x]) {
        // Increase width
        u = min(u, up[y][x]);
        d = min(d, down[y][x]);
        mx_height[++idx] = min(mx_height[idx], u+d-1);
      } else {
        u = d = 1e9;
        idx = 0;
      }
    }

    d = u = 1e9; idx = 0;
    for (int x = m; x >= 1; x--) {
      if (A[y][x]) {
        // Increase width
        u = min(u, up[y][x]);
        d = min(d, down[y][x]);
        mx_height[++idx] = min(mx_height[idx], u+d-1);
      } else {
        u = d = 1e9;
        idx = 0;
      }
    }
  }

  int ans = 0;
  int cr = mx_height[1];
  FOR(w,1,W+1) {
    cr = min(cr, mx_height[w]);
    ans = max(ans, w * cr);
  }

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

Test details

Test 1

Group: 1

Verdict:

input
1 20
00001111101110011110

correct output
3

user output
0

Test 2

Group: 2

Verdict:

input
20 1
1
1
1
0
...

correct output
2

user output
0

Test 3

Group: 3

Verdict:

input
2499 1
1
1
1
1
...

correct output
38

user output
0

Test 4

Group: 4

Verdict:

input
2499 1
1
1
1
1
...

correct output
55

user output
0

Test 5

Group: 5

Verdict:

input
1 2500
111111111110111111111110111111...

correct output
7

user output
0

Test 6

Group: 6

Verdict:

input
1 1000
111111111111111111111111111111...

correct output
33

user output
0

Test 7

Group: 7

Verdict:

input
5 5
11111
11111
11011
11111
...

correct output
4

user output
0

Test 8

Group: 8

Verdict:

input
20 20
11111000000000000000
11111000000000000000
11111100000000000000
11111111111000000000
...

correct output
8

user output
0

Test 9

Group: 9

Verdict:

input
20 20
11111100000000000000
11111100000000000000
11111110000000000000
11111111111110000000
...

correct output
12

user output
0

Test 10

Group: 10

Verdict:

input
14 13
0000011100000
0000011100000
0000011100000
0000011110000
...

correct output
4

user output
0

Test 11

Group: 11

Verdict:

input
20 19
1111110000000000000
1111111000000000000
1111111000000000000
1111111000000000000
...

correct output
10

user output
0

Test 12

Group: 12

Verdict:

input
15 15
110000000000000
110000000000000
110000000000000
111000000000000
...

correct output
2

user output
0

Test 13

Group: 13

Verdict:

input
15 11
00111000000
00111000000
00111000000
00111000000
...

correct output
3

user output
0

Test 14

Group: 14

Verdict:

input
16 16
0000111100001111
0000111100001111
0000111100001111
0000111100001111
...

correct output
16

user output
0

Test 15

Group: 15

Verdict:

input
18 18
111110000000000000
111110000000000000
111110000000000000
111111000000000000
...

correct output
8

user output
0

Test 16

Group: 16

Verdict:

input
20 20
11111111111111011111
11111111111111011111
11111111111111011111
11111111111111111111
...

correct output
20

user output
0

Test 17

Group: 17

Verdict:

input
65 70
000000000000000011111000000000...

correct output
15

user output
0

Test 18

Group: 18

Verdict:

input
70 62
111100000000000000000000000000...

correct output
6

user output
0

Test 19

Group: 19

Verdict:

input
94 78
111111111111111100000000000000...

correct output
22

user output
0

Test 20

Group: 20

Verdict:

input
92 84
111111111111111110000000000000...

correct output
27

user output
0

Test 21

Group: 21

Verdict:

input
53 89
000001111000000000000000000000...

correct output
6

user output
0

Test 22

Group: 22

Verdict:

input
76 93
000011111100000000000000000000...

correct output
12

user output
0

Test 23

Group: 23

Verdict:

input
100 100
111111111111111111111111111111...

correct output
209

user output
0

Test 24

Group: 24

Verdict:

input
81 74
111111111111111110000000000000...

correct output
30

user output
0

Test 25

Group: 25

Verdict:

input
100 100
111111111111111111111111111111...

correct output
80

user output
0

Test 26

Group: 26

Verdict:

input
100 100
111111111111111111111111111111...

correct output
132

user output
0

Test 27

Group: 27

Verdict:

input
295 268
111111111111111111111111111111...

correct output
3

user output
0

Test 28

Group: 28

Verdict:

input
290 383
111111110000000000000000000000...

correct output
20

user output
0

Test 29

Group: 29

Verdict:

input
390 320
000000000000000000000000000000...

correct output
3038

user output
0

Test 30

Group: 30

Verdict:

input
432 434
111111111111111111111111111111...

correct output
221

user output
0

Test 31

Group: 31

Verdict:

input
334 450
111111111111111111111111111111...

correct output
391

user output
0

Test 32

Group: 32

Verdict:

input
407 383
111111111111111111111111111111...

correct output
156

user output
0

Test 33

Group: 33

Verdict:

input
450 450
111111111111111111111111111111...

correct output
1235

user output
0

Test 34

Group: 34

Verdict:

input
356 231
000000000001111111111110000000...

correct output
42

user output
0

Test 35

Group: 35

Verdict:

input
450 450
111111111111111111111111111111...

correct output
192

user output
0

Test 36

Group: 36

Verdict:

input
450 450
111111111111111111111111111111...

correct output
1404

user output
0

Test 37

Group: 37

Verdict:

input
20 20
00000000001111111111
00000000001111111111
00000000001111111111
00000000001111111111
...

correct output
14

user output
0

Test 38

Group: 38

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
6250000

user output
0

Test 39

Group: 39

Verdict:

input
20 20
00000000001111111111
00000000001111111111
00000000111111111111
00000001111111111111
...

correct output
24

user output
0

Test 40

Group: 40

Verdict:

input
875 882
111111111111111111111111111111...

correct output
69552

user output
0

Test 41

Group: 41

Verdict:

input
20 20
00000000111111111111
00000011111111111111
00000011111111111111
00000111111111111111
...

correct output
36

user output
0

Test 42

Group: 42

Verdict:

input
100 100
000000000000000000000000000000...

correct output
651

user output
0

Test 43

Group: 43

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
250500

user output
0

Test 44

Group: 44

Verdict:

input
450 450
000000000000000000000000000000...

correct output
12864

user output
0

Test 45

Group: 45

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
399456

user output
0

Test 46

Group: 46

Verdict:

input
2500 2500
111111111111111111111111100000...

correct output
625

user output
0

Test 47

Group: 47

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
395486

user output
0

Test 48

Group: 48

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
3360

user output
0

Test 49

Group: 49

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
28

user output
0

Test 50

Group: 50

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
7348

user output
0

Test 51

Group: 51

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
6622

user output
0

Test 52

Group: 52

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
5593

user output
0

Test 53

Group: 53

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
4545

user output
0

Test 54

Group: 54

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
4067

user output
0

Test 55

Group: 55

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
2806

user output
0

Test 56

Group: 56

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
122500

user output
0

Test 57

Group: 57

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
4674

user output
0

Test 58

Group: 58

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
6272

user output
0

Test 59

Group: 59

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
3337

user output
0

Test 60

Group: 60

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
870

user output
0

Test 61

Group: 61

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
532

user output
0

Test 62

Group: 62

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
114271

user output
0

Test 63

Group: 63

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
1560001

user output
0

Test 64

Group: 64

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
62500

user output
0

Test 65

Group: 65

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
1400

user output
0

Test 66

Group: 66

Verdict:

input
2500 2500
000000111111111111111111111111...

correct output
9910

user output
0

Test 67

Group: 67

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
9879

user output
0

Test 68

Group: 68

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
16224

user output
0

Test 69

Group: 69

Verdict:

input
2500 2500
000000000000000000000000000000...

correct output
6300

user output
0

Test 70

Group: 70

Verdict:

input
2000 2000
111111111111111111111111111111...

correct output
59760

user output
0

Test 71

Group: 71

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
40480

user output
0

Test 72

Group: 72

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
137159

user output
0

Test 73

Group: 73

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
32110

user output
0

Test 74

Group: 74

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
10914

user output
0

Test 75

Group: 75

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
124074

user output
0

Test 76

Group: 76

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
4617

user output
0

Test 77

Group: 77

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
106981

user output
0

Test 78

Group: 78

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
44980

user output
0

Test 79

Group: 79

Verdict:

input
2500 2500
111111111111111111111111110000...

correct output
1365

user output
0

Test 80

Group: 80

Verdict:

input
2500 2500
111111111111111111110000000000...

correct output
602

user output
0

Test 81

Group: 81

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
2709

user output
0

Test 82

Group: 82

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
149556

user output
0

Test 83

Group: 83

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
11289

user output
0

Test 84

Group: 84

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
366

user output
0

Test 85

Group: 85

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
4814

user output
0

Test 86

Group: 86

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
132

user output
0

Test 87

Group: 87

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
589

user output
0

Test 88

Group: 88

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
56448

user output
0

Test 89

Group: 89

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
10044

user output
0

Test 90

Group: 90

Verdict:

input
2000 2000
111111111111111111111111111111...

correct output
6384

user output
0

Test 91

Group: 91

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
15330

user output
0

Test 92

Group: 92

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
47759

user output
0

Test 93

Group: 93

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
624

user output
0

Test 94

Group: 94

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
16695

user output
0

Test 95

Group: 95

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
19224

user output
0

Test 96

Group: 96

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
89386

user output
0

Test 97

Group: 97

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
243

user output
0

Test 98

Group: 98

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
73840

user output
0

Test 99

Group: 99

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
10764

user output
0

Test 100

Group: 100

Verdict:

input
2500 2500
111111111111111111111111111111...

correct output
135

user output
0