oj.uz

Submission #170916

# Submission time Handle Problem Language Result Execution time Memory
170916 2019-12-26T17:43:06 Z davitmarg Bomb (IZhO17_bomb) C++17
75 / 100
 1000 ms 75896 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--;
    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 (j == 1 || 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 (j == 1 || 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]);
    }
    cout << ans << endl;
    return 0;
}

/*
 
10 9
000000000
000111000
000111000
011111110
011101110
011111110
000111000
000111000
000000000
000000000


6 6
111000
111000
111100
001111
000111
000111

6 6
000111
000111
001111
111100
111000
111000
 
*/

Compilation message

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

Subtask #1
75.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 37 ms 30456 KB Output is correct
4 Correct 38 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 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 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 1144 KB Output is correct
18 Correct 3 ms 1272 KB Output is correct
19 Correct 4 ms 1528 KB Output is correct
20 Incorrect 4 ms 1528 KB Output isn't correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 3 ms 1272 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 13 ms 4828 KB Output is correct
28 Incorrect 13 ms 5240 KB Output isn't correct
29 Incorrect 18 ms 6584 KB Output isn't correct
30 Correct 22 ms 7928 KB Output is correct
31 Correct 17 ms 6264 KB Output is correct
32 Correct 19 ms 7288 KB Output is correct
33 Incorrect 23 ms 8312 KB Output isn't correct
34 Incorrect 12 ms 5624 KB Output isn't correct
35 Correct 23 ms 8312 KB Output is correct
36 Correct 26 ms 8312 KB Output is correct
37 Correct 2 ms 632 KB Output is correct
38 Correct 983 ms 75496 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 118 ms 20712 KB Output isn't correct
41 Correct 2 ms 504 KB Output is correct
42 Correct 4 ms 1656 KB Output is correct
43 Correct 861 ms 75616 KB Output is correct
44 Correct 25 ms 8312 KB Output is correct
45 Incorrect 851 ms 75724 KB Output isn't correct
46 Correct 826 ms 75716 KB Output is correct
47 Incorrect 862 ms 75728 KB Output isn't correct
48 Correct 837 ms 75844 KB Output is correct
49 Correct 993 ms 75844 KB Output is correct
50 Correct 830 ms 75700 KB Output is correct
51 Correct 826 ms 75628 KB Output is correct
52 Correct 840 ms 75672 KB Output is correct
53 Correct 833 ms 75612 KB Output is correct
54 Correct 742 ms 75768 KB Output is correct
55 Incorrect 725 ms 75896 KB Output isn't correct
56 Execution timed out 1049 ms 75752 KB Time limit exceeded
57 Incorrect 688 ms 75868 KB Output isn't correct
58 Correct 701 ms 75728 KB Output is correct
59 Correct 691 ms 75592 KB Output is correct
60 Correct 796 ms 75784 KB Output is correct
61 Correct 979 ms 75732 KB Output is correct
62 Correct 995 ms 75696 KB Output is correct
63 Correct 986 ms 75636 KB Output is correct
64 Correct 678 ms 75768 KB Output is correct
65 Correct 826 ms 75768 KB Output is correct
66 Correct 819 ms 75732 KB Output is correct
67 Correct 850 ms 75720 KB Output is correct
68 Correct 871 ms 75640 KB Output is correct
69 Correct 694 ms 75600 KB Output is correct
70 Incorrect 387 ms 60920 KB Output isn't correct
71 Correct 637 ms 75656 KB Output is correct
72 Incorrect 679 ms 75512 KB Output isn't correct
73 Correct 700 ms 75640 KB Output is correct
74 Correct 684 ms 75696 KB Output is correct
75 Correct 700 ms 75640 KB Output is correct
76 Incorrect 705 ms 75568 KB Output isn't correct
77 Incorrect 707 ms 75520 KB Output isn't correct
78 Incorrect 704 ms 75512 KB Output isn't correct
79 Correct 559 ms 75528 KB Output is correct
80 Correct 559 ms 75620 KB Output is correct
81 Correct 586 ms 75412 KB Output is correct
82 Incorrect 736 ms 75512 KB Output isn't correct
83 Correct 727 ms 75384 KB Output is correct
84 Correct 554 ms 75256 KB Output is correct
85 Correct 725 ms 75512 KB Output is correct
86 Correct 937 ms 75424 KB Output is correct
87 Incorrect 686 ms 75460 KB Output isn't correct
88 Correct 717 ms 75384 KB Output is correct
89 Correct 781 ms 75408 KB Output is correct
90 Correct 425 ms 60664 KB Output is correct
91 Incorrect 741 ms 75256 KB Output isn't correct
92 Incorrect 786 ms 75356 KB Output isn't correct
93 Incorrect 938 ms 75496 KB Output isn't correct
94 Correct 779 ms 75312 KB Output is correct
95 Correct 718 ms 75416 KB Output is correct
96 Correct 718 ms 75256 KB Output is correct
97 Incorrect 932 ms 75320 KB Output isn't correct
98 Incorrect 713 ms 75128 KB Output isn't correct
99 Correct 773 ms 75128 KB Output is correct
100 Correct 920 ms 75000 KB Output is correct