oj.uz

Submission #170422

# Submission time Handle Problem Language Result Execution time Memory
170422 2019-12-25T07:40:36 Z davitmarg Bomb (IZhO17_bomb) C++17
51 / 100
 614 ms 50440 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 2505;

int n, m, a[N][N], nxt[N][N], d[N], Y, X, ans;

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char x;
            scanf(" %c", &x);
            a[i][j] += (x - '0');
        }
    X = m;
    Y = n;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
        {
            if (a[i][j])
                nxt[i][j] = nxt[i][j + 1] + 1;
            else
                nxt[i][j] = 0;
            if (a[i][j - 1] == 0 && a[i][j])
                X = min(X, nxt[i][j]);
        }
    for (int j = 1; j <= m; j++)
    {
        int y = 0;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j])
                y++;
            else
                y = 0;
            if (a[i][j] && a[i + 1][j] == 0)
                Y = min(y, Y);
        }
    }

    for (int i = 1; i <= Y; i++)
        d[i] = X;
    for (int j = 1; j <= m; j++)
    {
        int y = 0, x = X;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j] == 0 || ((a[i][j - 1] == 1 || a[i - 1][j] == 1) && y == 0))
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                d[y] = min(x, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }
    }

    for (int j = 1; j <= m; j++)
    {
        int y = 0, x = X;
        for (int i = n; i >= 1; i--)
        {
            if (a[i][j] == 0 || ((a[i][j - 1] == 1 || a[i + 1][j] == 1) && y == 0))
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                d[y] = min(x, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }
    }

    for (int i = 1; i <= Y; i++)
    {
        //d[i + 1] = min(d[i + 1], d[i]);
        //cout << i << " : " << d[i] << endl;
        ans = max(ans, i * d[i]);
    }
    cout << ans << endl;
    return 0;
}

/*

10 8
00000000
00111000
00111000
11111110
11101110
11111110
00111000
00111000
00000000
00000000
 
6 6
000111
000111
001111
111100
111000
111000
 
*/

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &x);
             ~~~~~^~~~~~~~~~~

Subtask #1
51.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 21 ms 20344 KB Output is correct
4 Correct 21 ms 20344 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 Incorrect 2 ms 504 KB Output isn't correct
9 Incorrect 2 ms 504 KB Output isn't correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Incorrect 2 ms 504 KB Output isn't correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 3 ms 1016 KB Output is correct
18 Correct 3 ms 888 KB Output is correct
19 Incorrect 3 ms 1144 KB Output isn't correct
20 Incorrect 3 ms 1144 KB Output isn't correct
21 Correct 3 ms 764 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Incorrect 3 ms 1144 KB Output isn't correct
24 Incorrect 3 ms 1020 KB Output isn't correct
25 Incorrect 3 ms 1144 KB Output isn't correct
26 Correct 3 ms 1144 KB Output is correct
27 Correct 10 ms 3320 KB Output is correct
28 Incorrect 11 ms 3680 KB Output isn't correct
29 Incorrect 13 ms 4632 KB Output isn't correct
30 Incorrect 17 ms 5520 KB Output isn't correct
31 Correct 14 ms 4344 KB Output is correct
32 Incorrect 14 ms 4984 KB Output isn't correct
33 Incorrect 18 ms 5752 KB Output isn't correct
34 Incorrect 9 ms 3960 KB Output isn't correct
35 Incorrect 18 ms 5752 KB Output isn't correct
36 Correct 19 ms 5752 KB Output is correct
37 Incorrect 2 ms 504 KB Output isn't correct
38 Correct 556 ms 50124 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 65 ms 13688 KB Output isn't correct
41 Correct 2 ms 504 KB Output is correct
42 Correct 3 ms 1248 KB Output is correct
43 Correct 568 ms 50212 KB Output is correct
44 Correct 18 ms 5756 KB Output is correct
45 Incorrect 559 ms 50356 KB Output isn't correct
46 Correct 533 ms 50424 KB Output is correct
47 Incorrect 556 ms 50136 KB Output isn't correct
48 Correct 535 ms 50244 KB Output is correct
49 Correct 568 ms 50168 KB Output is correct
50 Correct 539 ms 50108 KB Output is correct
51 Correct 534 ms 50124 KB Output is correct
52 Correct 536 ms 50168 KB Output is correct
53 Correct 534 ms 50228 KB Output is correct
54 Correct 516 ms 50124 KB Output is correct
55 Incorrect 518 ms 50200 KB Output isn't correct
56 Correct 561 ms 50416 KB Output is correct
57 Incorrect 514 ms 50168 KB Output isn't correct
58 Correct 548 ms 50304 KB Output is correct
59 Correct 514 ms 50296 KB Output is correct
60 Correct 587 ms 50296 KB Output is correct
61 Correct 560 ms 50168 KB Output is correct
62 Correct 559 ms 50168 KB Output is correct
63 Correct 576 ms 50236 KB Output is correct
64 Correct 518 ms 50184 KB Output is correct
65 Correct 528 ms 50168 KB Output is correct
66 Correct 531 ms 50184 KB Output is correct
67 Correct 538 ms 50296 KB Output is correct
68 Correct 614 ms 50368 KB Output is correct
69 Correct 512 ms 50300 KB Output is correct
70 Incorrect 309 ms 40312 KB Output isn't correct
71 Incorrect 504 ms 50168 KB Output isn't correct
72 Incorrect 509 ms 50296 KB Output isn't correct
73 Correct 515 ms 50300 KB Output is correct
74 Incorrect 552 ms 50116 KB Output isn't correct
75 Incorrect 513 ms 50164 KB Output isn't correct
76 Incorrect 512 ms 50296 KB Output isn't correct
77 Incorrect 546 ms 50168 KB Output isn't correct
78 Incorrect 511 ms 50168 KB Output isn't correct
79 Incorrect 488 ms 50168 KB Output isn't correct
80 Incorrect 490 ms 50256 KB Output isn't correct
81 Incorrect 498 ms 50300 KB Output isn't correct
82 Incorrect 516 ms 50296 KB Output isn't correct
83 Incorrect 514 ms 50148 KB Output isn't correct
84 Incorrect 495 ms 50156 KB Output isn't correct
85 Incorrect 510 ms 50160 KB Output isn't correct
86 Incorrect 551 ms 50296 KB Output isn't correct
87 Incorrect 509 ms 50296 KB Output isn't correct
88 Correct 511 ms 50296 KB Output is correct
89 Correct 550 ms 50248 KB Output is correct
90 Incorrect 317 ms 40188 KB Output isn't correct
91 Incorrect 520 ms 50324 KB Output isn't correct
92 Incorrect 525 ms 50296 KB Output isn't correct
93 Incorrect 571 ms 50440 KB Output isn't correct
94 Correct 526 ms 50040 KB Output is correct
95 Incorrect 512 ms 49616 KB Output isn't correct
96 Correct 512 ms 49784 KB Output is correct
97 Incorrect 551 ms 49728 KB Output isn't correct
98 Incorrect 513 ms 49656 KB Output isn't correct
99 Incorrect 528 ms 49680 KB Output isn't correct
100 Incorrect 551 ms 49656 KB Output isn't correct