oj.uz

Submission #170975

# Submission time Handle Problem Language Result Execution time Memory
170975 2019-12-26T21:16:51 Z davitmarg Bomb (IZhO17_bomb) C++17
76 / 100
 964 ms 74220 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], pr[N][N], nxt[N][N], d[N], Y, X, ans;

int get(int sy, int sx, int y, int x)
{
    sy--;
    sx--;
    if (sy == -1 || sx == -1)
        return pr[y][x];
    return pr[y][x] - pr[sy][x] - pr[y][sx] + pr[sy][sx];
}

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');
            pr[i][j] = a[i][j] + pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];
        }
    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)
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                if (get(i - y + 1, j - 1, i, j - 1) != y)
                    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)
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                if (get(i, j - 1, i + y - 1, j - 1) != y)
                    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]);
    }
    assert(ans != 0);

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

/*

2 2
00
00

5 6
100000
111110
111110
111110
100000

6 5
00110
01110
11110
11011
11111
11111


9 9
000000000
000111000
000111000
011111110
011101110
011111110
000111000
000111000
000000000
 
9 9
000000000
000111000
000111000
011111110
011101110
011111110
000111000
000111000
000000000

6 6
000111
000111
001111
111100
111000
111000

6 6
000000
111000
111100
001111
000111
000111

6 6
000111
011111
011111
111000
111000
111000
 
*/

Compilation message

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

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 36 ms 30460 KB Output is correct
4 Correct 36 ms 30456 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 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 3 ms 1148 KB Output is correct
18 Correct 3 ms 1272 KB Output is correct
19 Correct 4 ms 1528 KB Output is correct
20 Incorrect 3 ms 1528 KB Output isn't correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 3 ms 1400 KB Output is correct
23 Correct 4 ms 1656 KB Output is correct
24 Correct 3 ms 1400 KB Output is correct
25 Incorrect 4 ms 1656 KB Output isn't correct
26 Correct 4 ms 1656 KB Output is correct
27 Correct 12 ms 4856 KB Output is correct
28 Incorrect 13 ms 5112 KB Output isn't correct
29 Incorrect 17 ms 6492 KB Output isn't correct
30 Correct 22 ms 7800 KB Output is correct
31 Correct 17 ms 6136 KB Output is correct
32 Correct 18 ms 7032 KB Output is correct
33 Incorrect 23 ms 8056 KB Output isn't correct
34 Incorrect 12 ms 5496 KB Output isn't correct
35 Correct 22 ms 8056 KB Output is correct
36 Correct 26 ms 8184 KB Output is correct
37 Correct 2 ms 632 KB Output is correct
38 Correct 955 ms 73888 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 113 ms 19960 KB Output isn't correct
41 Correct 2 ms 632 KB Output is correct
42 Correct 4 ms 1660 KB Output is correct
43 Correct 834 ms 73888 KB Output is correct
44 Correct 24 ms 8056 KB Output is correct
45 Incorrect 828 ms 73908 KB Output isn't correct
46 Correct 792 ms 74220 KB Output is correct
47 Incorrect 829 ms 73948 KB Output isn't correct
48 Correct 794 ms 73920 KB Output is correct
49 Correct 955 ms 74032 KB Output is correct
50 Correct 807 ms 73976 KB Output is correct
51 Correct 817 ms 73856 KB Output is correct
52 Correct 798 ms 73948 KB Output is correct
53 Correct 807 ms 73976 KB Output is correct
54 Correct 692 ms 73956 KB Output is correct
55 Incorrect 681 ms 73948 KB Output isn't correct
56 Correct 956 ms 73964 KB Output is correct
57 Incorrect 696 ms 73976 KB Output isn't correct
58 Correct 694 ms 73988 KB Output is correct
59 Correct 666 ms 73976 KB Output is correct
60 Correct 790 ms 73956 KB Output is correct
61 Correct 963 ms 73976 KB Output is correct
62 Correct 960 ms 73984 KB Output is correct
63 Correct 964 ms 74016 KB Output is correct
64 Correct 663 ms 73860 KB Output is correct
65 Correct 788 ms 73972 KB Output is correct
66 Correct 790 ms 74036 KB Output is correct
67 Correct 815 ms 74036 KB Output is correct
68 Correct 841 ms 73976 KB Output is correct
69 Correct 672 ms 74056 KB Output is correct
70 Incorrect 372 ms 59256 KB Output isn't correct
71 Correct 614 ms 73848 KB Output is correct
72 Incorrect 661 ms 73976 KB Output isn't correct
73 Correct 673 ms 74104 KB Output is correct
74 Correct 667 ms 74044 KB Output is correct
75 Correct 682 ms 73976 KB Output is correct
76 Incorrect 681 ms 73848 KB Output isn't correct
77 Incorrect 697 ms 73848 KB Output isn't correct
78 Incorrect 693 ms 73824 KB Output isn't correct
79 Correct 545 ms 74008 KB Output is correct
80 Correct 542 ms 73880 KB Output is correct
81 Correct 563 ms 73924 KB Output is correct
82 Incorrect 698 ms 73856 KB Output isn't correct
83 Correct 697 ms 73844 KB Output is correct
84 Correct 545 ms 73848 KB Output is correct
85 Correct 678 ms 74104 KB Output is correct
86 Correct 914 ms 73848 KB Output is correct
87 Incorrect 663 ms 73848 KB Output isn't correct
88 Correct 697 ms 73840 KB Output is correct
89 Correct 767 ms 73976 KB Output is correct
90 Correct 417 ms 59192 KB Output is correct
91 Incorrect 748 ms 73884 KB Output isn't correct
92 Incorrect 783 ms 73976 KB Output isn't correct
93 Incorrect 909 ms 73976 KB Output isn't correct
94 Correct 760 ms 73956 KB Output is correct
95 Correct 715 ms 73988 KB Output is correct
96 Correct 703 ms 74068 KB Output is correct
97 Incorrect 915 ms 73976 KB Output isn't correct
98 Incorrect 699 ms 73976 KB Output isn't correct
99 Correct 758 ms 74016 KB Output is correct
100 Correct 901 ms 74104 KB Output is correct