oj.uz

Submission #170418

# Submission time Handle Problem Language Result Execution time Memory
170418 2019-12-25T06:38:33 Z davitmarg Bomb (IZhO17_bomb) C++17
43 / 100
 576 ms 52344 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 <= n; 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 && 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 && 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++)
        ans = max(ans, i * d[i]);

    cout << ans << endl;
    return 0;
}

/*

8 8
00000000
01111100
01111100
01111100
01101100
01111100
01111100
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
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 23 ms 20472 KB Output is correct
4 Correct 21 ms 20472 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 508 KB Output isn't correct
9 Incorrect 2 ms 504 KB Output isn't correct
10 Correct 2 ms 504 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 504 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Incorrect 2 ms 504 KB Output isn't correct
16 Correct 2 ms 504 KB Output is correct
17 Incorrect 3 ms 1016 KB Output isn't 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 760 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 1016 KB Output isn't correct
25 Incorrect 3 ms 1144 KB Output isn't correct
26 Incorrect 3 ms 1144 KB Output isn't correct
27 Correct 10 ms 3448 KB Output is correct
28 Incorrect 11 ms 3704 KB Output isn't correct
29 Incorrect 13 ms 4604 KB Output isn't correct
30 Incorrect 17 ms 5496 KB Output isn't correct
31 Correct 15 ms 4300 KB Output is correct
32 Incorrect 14 ms 4956 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 17 ms 5752 KB Output isn't correct
36 Incorrect 19 ms 5752 KB Output isn't correct
37 Incorrect 2 ms 504 KB Output isn't correct
38 Correct 564 ms 52148 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 62 ms 14200 KB Output isn't correct
41 Correct 2 ms 504 KB Output is correct
42 Correct 3 ms 1272 KB Output is correct
43 Correct 559 ms 52344 KB Output is correct
44 Correct 18 ms 5752 KB Output is correct
45 Incorrect 551 ms 52180 KB Output isn't correct
46 Correct 525 ms 52204 KB Output is correct
47 Incorrect 558 ms 52088 KB Output isn't correct
48 Incorrect 527 ms 52124 KB Output isn't correct
49 Correct 560 ms 52288 KB Output is correct
50 Incorrect 525 ms 52088 KB Output isn't correct
51 Incorrect 524 ms 51864 KB Output isn't correct
52 Correct 534 ms 52080 KB Output is correct
53 Correct 536 ms 51960 KB Output is correct
54 Correct 506 ms 52044 KB Output is correct
55 Incorrect 520 ms 51704 KB Output isn't correct
56 Correct 548 ms 51416 KB Output is correct
57 Incorrect 507 ms 51416 KB Output isn't correct
58 Correct 504 ms 51448 KB Output is correct
59 Correct 508 ms 51340 KB Output is correct
60 Correct 576 ms 51320 KB Output is correct
61 Correct 561 ms 52008 KB Output is correct
62 Correct 542 ms 51860 KB Output is correct
63 Correct 540 ms 51960 KB Output is correct
64 Correct 505 ms 51832 KB Output is correct
65 Correct 521 ms 51576 KB Output is correct
66 Correct 517 ms 51300 KB Output is correct
67 Incorrect 529 ms 51260 KB Output isn't correct
68 Incorrect 538 ms 51320 KB Output isn't correct
69 Correct 509 ms 51300 KB Output is correct
70 Incorrect 306 ms 41112 KB Output isn't correct
71 Incorrect 496 ms 51484 KB Output isn't correct
72 Incorrect 501 ms 51216 KB Output isn't correct
73 Correct 506 ms 51196 KB Output is correct
74 Incorrect 503 ms 51248 KB Output isn't correct
75 Incorrect 501 ms 51192 KB Output isn't correct
76 Incorrect 507 ms 51112 KB Output isn't correct
77 Incorrect 505 ms 50904 KB Output isn't correct
78 Incorrect 502 ms 50812 KB Output isn't correct
79 Incorrect 488 ms 50808 KB Output isn't correct
80 Incorrect 484 ms 50680 KB Output isn't correct
81 Incorrect 498 ms 50884 KB Output isn't correct
82 Incorrect 511 ms 50748 KB Output isn't correct
83 Incorrect 513 ms 51208 KB Output isn't correct
84 Incorrect 488 ms 51064 KB Output isn't correct
85 Incorrect 503 ms 51064 KB Output isn't correct
86 Incorrect 541 ms 51040 KB Output isn't correct
87 Incorrect 502 ms 51064 KB Output isn't correct
88 Correct 512 ms 50980 KB Output is correct
89 Correct 521 ms 50424 KB Output is correct
90 Incorrect 315 ms 40876 KB Output isn't correct
91 Incorrect 508 ms 50552 KB Output isn't correct
92 Incorrect 516 ms 50560 KB Output isn't correct
93 Incorrect 540 ms 50556 KB Output isn't correct
94 Correct 518 ms 50580 KB Output is correct
95 Incorrect 507 ms 50680 KB Output isn't correct
96 Correct 503 ms 50552 KB Output is correct
97 Incorrect 540 ms 50704 KB Output isn't correct
98 Incorrect 509 ms 50552 KB Output isn't correct
99 Incorrect 519 ms 50728 KB Output isn't correct
100 Incorrect 543 ms 50552 KB Output isn't correct