oj.uz

답안 #170981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170981 2019-12-26T21:44:04 Z davitmarg Bomb (IZhO17_bomb) C++17
4 / 100
 853 ms 74104 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], lst[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;
                if (a[i][j - 1])
                    X = min(nxt[i][j], X);
            }
            else
                nxt[i][j] = 0;
        }

        for (int j = 1; j <= m; j++)
            if (a[i][j])
                lst[i][j] = lst[i][j - 1] + 1;
            else
                lst[i][j] = 0;
    }

    for (int i = 1; i <= Y; i++)
        d[i] = X;

    for (int j = 1; j <= m; j++)
    {
        int y = 0, l = X, r = X;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j] == 0)
            {
                y = 0;
                l = r = X;
            }
            else
            {
                y++;
                r = min(r, nxt[i][j]);
                l = min(l, lst[i][j]);
                d[y] = min(l + r - 1, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }

        y = 0;
        l = X;
        r = X;
        for (int i = n; i >= 1; i--)
        {

            if (a[i][j] == 0)
            {
                y = 0;
                l = r = X;
            }
            else
            {
                y++;
                if (a[i - 1][j] == 0)
                    Y = min(y, Y);
                r = min(r, nxt[i][j]);
                l = min(l, lst[i][j]);
                d[y] = min(l + r - 1, 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;
}

/*

4 3
110
111
111
011

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:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &x);
             ~~~~~^~~~~~~~~~~

Subtask #1
4.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 33 ms 30456 KB Output is correct
4 Correct 33 ms 30456 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Incorrect 2 ms 632 KB Output isn't correct
9 Incorrect 2 ms 632 KB Output isn't correct
10 Incorrect 2 ms 504 KB Output isn't correct
11 Incorrect 2 ms 636 KB Output isn't correct
12 Correct 2 ms 504 KB Output is correct
13 Incorrect 2 ms 504 KB Output isn't correct
14 Incorrect 2 ms 504 KB Output isn't correct
15 Incorrect 2 ms 504 KB Output isn't correct
16 Incorrect 2 ms 632 KB Output isn't correct
17 Incorrect 3 ms 1144 KB Output isn't correct
18 Incorrect 3 ms 1272 KB Output isn't correct
19 Incorrect 3 ms 1500 KB Output isn't correct
20 Incorrect 3 ms 1656 KB Output isn't correct
21 Incorrect 3 ms 1016 KB Output isn't correct
22 Incorrect 3 ms 1400 KB Output isn't correct
23 Incorrect 3 ms 1656 KB Output isn't correct
24 Incorrect 3 ms 1400 KB Output isn't correct
25 Incorrect 3 ms 1660 KB Output isn't correct
26 Incorrect 4 ms 1656 KB Output isn't correct
27 Incorrect 12 ms 4856 KB Output isn't correct
28 Incorrect 12 ms 5112 KB Output isn't correct
29 Incorrect 15 ms 6520 KB Output isn't correct
30 Incorrect 19 ms 7672 KB Output isn't correct
31 Incorrect 15 ms 6140 KB Output isn't correct
32 Incorrect 17 ms 7004 KB Output isn't correct
33 Incorrect 21 ms 8184 KB Output isn't correct
34 Incorrect 11 ms 5624 KB Output isn't correct
35 Incorrect 20 ms 8060 KB Output isn't correct
36 Incorrect 24 ms 8184 KB Output isn't correct
37 Incorrect 2 ms 636 KB Output isn't correct
38 Incorrect 840 ms 74016 KB Output isn't correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 96 ms 19832 KB Output isn't correct
41 Incorrect 2 ms 504 KB Output isn't correct
42 Incorrect 3 ms 1656 KB Output isn't correct
43 Incorrect 729 ms 73944 KB Output isn't correct
44 Incorrect 26 ms 8184 KB Output isn't correct
45 Incorrect 712 ms 73964 KB Output isn't correct
46 Incorrect 668 ms 73848 KB Output isn't correct
47 Incorrect 716 ms 73980 KB Output isn't correct
48 Incorrect 682 ms 73976 KB Output isn't correct
49 Incorrect 834 ms 74056 KB Output isn't correct
50 Incorrect 701 ms 74088 KB Output isn't correct
51 Incorrect 696 ms 73964 KB Output isn't correct
52 Incorrect 692 ms 73924 KB Output isn't correct
53 Incorrect 693 ms 74060 KB Output isn't correct
54 Incorrect 598 ms 73812 KB Output isn't correct
55 Incorrect 598 ms 73988 KB Output isn't correct
56 Incorrect 824 ms 73880 KB Output isn't correct
57 Incorrect 585 ms 73960 KB Output isn't correct
58 Incorrect 593 ms 74104 KB Output isn't correct
59 Incorrect 589 ms 73912 KB Output isn't correct
60 Incorrect 675 ms 73976 KB Output isn't correct
61 Incorrect 853 ms 73976 KB Output isn't correct
62 Incorrect 835 ms 73932 KB Output isn't correct
63 Incorrect 830 ms 74020 KB Output isn't correct
64 Incorrect 590 ms 73944 KB Output isn't correct
65 Incorrect 673 ms 73976 KB Output isn't correct
66 Incorrect 678 ms 73976 KB Output isn't correct
67 Incorrect 712 ms 74008 KB Output isn't correct
68 Incorrect 733 ms 74104 KB Output isn't correct
69 Incorrect 619 ms 73976 KB Output isn't correct
70 Incorrect 338 ms 59380 KB Output isn't correct
71 Incorrect 546 ms 74104 KB Output isn't correct
72 Incorrect 577 ms 73872 KB Output isn't correct
73 Incorrect 593 ms 73848 KB Output isn't correct
74 Incorrect 583 ms 73948 KB Output isn't correct
75 Incorrect 589 ms 73900 KB Output isn't correct
76 Incorrect 600 ms 74104 KB Output isn't correct
77 Incorrect 604 ms 74008 KB Output isn't correct
78 Incorrect 599 ms 73964 KB Output isn't correct
79 Incorrect 491 ms 73948 KB Output isn't correct
80 Incorrect 485 ms 73976 KB Output isn't correct
81 Incorrect 497 ms 73848 KB Output isn't correct
82 Incorrect 608 ms 73972 KB Output isn't correct
83 Incorrect 612 ms 74036 KB Output isn't correct
84 Incorrect 492 ms 73848 KB Output isn't correct
85 Incorrect 620 ms 74004 KB Output isn't correct
86 Incorrect 797 ms 73980 KB Output isn't correct
87 Incorrect 590 ms 73964 KB Output isn't correct
88 Incorrect 609 ms 74104 KB Output isn't correct
89 Incorrect 661 ms 73916 KB Output isn't correct
90 Incorrect 371 ms 59240 KB Output isn't correct
91 Incorrect 622 ms 73976 KB Output isn't correct
92 Incorrect 663 ms 74088 KB Output isn't correct
93 Incorrect 786 ms 73952 KB Output isn't correct
94 Incorrect 660 ms 74024 KB Output isn't correct
95 Incorrect 607 ms 74104 KB Output isn't correct
96 Incorrect 604 ms 73888 KB Output isn't correct
97 Incorrect 802 ms 73976 KB Output isn't correct
98 Incorrect 625 ms 73976 KB Output isn't correct
99 Incorrect 651 ms 73976 KB Output isn't correct
100 Incorrect 783 ms 74040 KB Output isn't correct