oj.uz

Submission #170920

# Submission time Handle Problem Language Result Execution time Memory
170920 2019-12-26T17:50:46 Z davitmarg Bomb (IZhO17_bomb) C++17
67 / 100
 1000 ms 76124 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]);
        }
    X = m;
    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;
}

/*

2 2
11
10
 
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
67.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 42 ms 30480 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 Incorrect 2 ms 376 KB Output isn't correct
8 Correct 2 ms 504 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 632 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 508 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 2 ms 632 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 1532 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 Incorrect 4 ms 1656 KB Output isn't correct
27 Incorrect 12 ms 4984 KB Output isn't 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 7800 KB Output is correct
31 Correct 17 ms 6264 KB Output is correct
32 Correct 18 ms 7160 KB Output is correct
33 Incorrect 23 ms 8440 KB Output isn't correct
34 Incorrect 12 ms 5624 KB Output isn't correct
35 Correct 21 ms 8184 KB Output is correct
36 Incorrect 25 ms 8184 KB Output isn't correct
37 Correct 2 ms 504 KB Output is correct
38 Correct 951 ms 74076 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 112 ms 20088 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 823 ms 74216 KB Output is correct
44 Correct 23 ms 8184 KB Output is correct
45 Incorrect 813 ms 74364 KB Output isn't correct
46 Correct 792 ms 74232 KB Output is correct
47 Incorrect 819 ms 74232 KB Output isn't correct
48 Correct 783 ms 74240 KB Output is correct
49 Incorrect 951 ms 74104 KB Output isn't correct
50 Correct 801 ms 74232 KB Output is correct
51 Correct 797 ms 74260 KB Output is correct
52 Correct 796 ms 74232 KB Output is correct
53 Correct 795 ms 74232 KB Output is correct
54 Correct 726 ms 74192 KB Output is correct
55 Incorrect 703 ms 74232 KB Output isn't correct
56 Execution timed out 1073 ms 74116 KB Time limit exceeded
57 Incorrect 657 ms 74224 KB Output isn't correct
58 Correct 668 ms 74232 KB Output is correct
59 Correct 658 ms 74232 KB Output is correct
60 Correct 767 ms 74364 KB Output is correct
61 Incorrect 997 ms 74188 KB Output isn't correct
62 Incorrect 963 ms 74124 KB Output isn't correct
63 Incorrect 958 ms 74232 KB Output isn't correct
64 Correct 642 ms 74068 KB Output is correct
65 Correct 780 ms 74264 KB Output is correct
66 Correct 785 ms 74232 KB Output is correct
67 Correct 810 ms 74108 KB Output is correct
68 Correct 831 ms 74104 KB Output is correct
69 Correct 666 ms 74252 KB Output is correct
70 Incorrect 361 ms 59356 KB Output isn't correct
71 Correct 600 ms 74232 KB Output is correct
72 Incorrect 651 ms 74904 KB Output isn't correct
73 Correct 660 ms 75748 KB Output is correct
74 Correct 652 ms 76024 KB Output is correct
75 Correct 700 ms 76024 KB Output is correct
76 Incorrect 660 ms 75896 KB Output isn't correct
77 Incorrect 675 ms 76124 KB Output isn't correct
78 Incorrect 689 ms 76044 KB Output isn't correct
79 Correct 521 ms 75928 KB Output is correct
80 Correct 524 ms 75936 KB Output is correct
81 Correct 531 ms 75768 KB Output is correct
82 Incorrect 686 ms 75928 KB Output isn't correct
83 Correct 690 ms 76100 KB Output is correct
84 Correct 523 ms 76016 KB Output is correct
85 Correct 665 ms 75740 KB Output is correct
86 Correct 933 ms 75908 KB Output is correct
87 Incorrect 652 ms 75728 KB Output isn't correct
88 Correct 693 ms 75768 KB Output is correct
89 Correct 758 ms 75504 KB Output is correct
90 Correct 406 ms 60792 KB Output is correct
91 Incorrect 709 ms 75672 KB Output isn't correct
92 Incorrect 750 ms 75640 KB Output isn't correct
93 Incorrect 930 ms 75516 KB Output isn't correct
94 Correct 806 ms 75432 KB Output is correct
95 Correct 709 ms 75512 KB Output is correct
96 Correct 685 ms 75512 KB Output is correct
97 Incorrect 916 ms 75384 KB Output isn't correct
98 Incorrect 695 ms 75520 KB Output isn't correct
99 Correct 761 ms 75384 KB Output is correct
100 Correct 899 ms 75536 KB Output is correct