oj.uz

Submission #170915

# Submission time Handle Problem Language Result Execution time Memory
170915 2019-12-26T17:41:22 Z davitmarg Bomb (IZhO17_bomb) C++17
75 / 100
 1000 ms 76420 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 (sx == -1 || sy == -1)
        return 0;
    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]);
    }
    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:47: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 504 KB Output is correct
3 Correct 37 ms 30500 KB Output is correct
4 Correct 37 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 632 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 3 ms 1144 KB Output is correct
18 Correct 4 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 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 5240 KB Output isn't correct
29 Incorrect 17 ms 6648 KB Output isn't correct
30 Correct 21 ms 7928 KB Output is correct
31 Correct 17 ms 6264 KB Output is correct
32 Correct 18 ms 7196 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 22 ms 8440 KB Output is correct
36 Correct 26 ms 8316 KB Output is correct
37 Correct 2 ms 632 KB Output is correct
38 Correct 959 ms 76420 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 114 ms 20600 KB Output isn't correct
41 Correct 2 ms 508 KB Output is correct
42 Correct 4 ms 1656 KB Output is correct
43 Correct 842 ms 76380 KB Output is correct
44 Correct 24 ms 8312 KB Output is correct
45 Incorrect 907 ms 76292 KB Output isn't correct
46 Correct 818 ms 76408 KB Output is correct
47 Incorrect 829 ms 76408 KB Output isn't correct
48 Correct 809 ms 76400 KB Output is correct
49 Correct 954 ms 76408 KB Output is correct
50 Correct 804 ms 76280 KB Output is correct
51 Correct 804 ms 76284 KB Output is correct
52 Correct 816 ms 76280 KB Output is correct
53 Correct 802 ms 76284 KB Output is correct
54 Correct 680 ms 76152 KB Output is correct
55 Incorrect 671 ms 76152 KB Output isn't correct
56 Execution timed out 1016 ms 76208 KB Time limit exceeded
57 Incorrect 655 ms 76152 KB Output isn't correct
58 Correct 698 ms 76112 KB Output is correct
59 Correct 660 ms 76024 KB Output is correct
60 Correct 765 ms 75996 KB Output is correct
61 Correct 941 ms 76236 KB Output is correct
62 Correct 949 ms 76024 KB Output is correct
63 Correct 947 ms 76000 KB Output is correct
64 Correct 644 ms 76008 KB Output is correct
65 Correct 775 ms 75856 KB Output is correct
66 Correct 783 ms 75920 KB Output is correct
67 Correct 813 ms 75768 KB Output is correct
68 Correct 837 ms 75896 KB Output is correct
69 Correct 663 ms 75616 KB Output is correct
70 Incorrect 361 ms 61160 KB Output isn't correct
71 Correct 602 ms 75768 KB Output is correct
72 Incorrect 659 ms 75644 KB Output isn't correct
73 Correct 662 ms 75512 KB Output is correct
74 Correct 661 ms 75656 KB Output is correct
75 Correct 662 ms 75420 KB Output is correct
76 Incorrect 675 ms 75584 KB Output isn't correct
77 Incorrect 677 ms 75528 KB Output isn't correct
78 Incorrect 690 ms 75384 KB Output isn't correct
79 Correct 536 ms 75360 KB Output is correct
80 Correct 527 ms 75312 KB Output is correct
81 Correct 563 ms 75224 KB Output is correct
82 Incorrect 698 ms 75360 KB Output isn't correct
83 Correct 700 ms 75512 KB Output is correct
84 Correct 530 ms 75256 KB Output is correct
85 Correct 670 ms 75200 KB Output is correct
86 Correct 908 ms 75136 KB Output is correct
87 Incorrect 662 ms 75356 KB Output isn't correct
88 Correct 691 ms 75000 KB Output is correct
89 Correct 774 ms 75012 KB Output is correct
90 Correct 409 ms 60284 KB Output is correct
91 Incorrect 707 ms 75012 KB Output isn't correct
92 Incorrect 752 ms 75248 KB Output isn't correct
93 Incorrect 927 ms 74852 KB Output isn't correct
94 Correct 775 ms 75008 KB Output is correct
95 Correct 696 ms 74872 KB Output is correct
96 Correct 699 ms 74744 KB Output is correct
97 Incorrect 918 ms 74744 KB Output isn't correct
98 Incorrect 685 ms 74488 KB Output isn't correct
99 Correct 745 ms 74600 KB Output is correct
100 Correct 895 ms 74744 KB Output is correct