oj.uz

답안 #170420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
170420 2019-12-25T07:02:16 Z davitmarg Bomb (IZhO17_bomb) C++17
43 / 100
 618 ms 51924 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], 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;
            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 <= n; 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 || (a[i][j - 1] == 1 && y == 0))
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                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 || (a[i][j - 1] == 1 && y == 0))
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                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]);
        ans = max(ans, i * d[i]);
    }
    cout << ans << endl;
    return 0;
}

/*

8 8
00000000
01111100
01111100
01111100
01101100
01111100
01111100
00000000
 
6 6
000111
000111
001111
111100
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
43.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 21 ms 20472 KB Output is correct
4 Correct 22 ms 20476 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 Incorrect 2 ms 504 KB Output isn't correct
9 Incorrect 2 ms 504 KB Output isn't correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Incorrect 2 ms 508 KB Output isn't correct
16 Correct 2 ms 504 KB Output is correct
17 Incorrect 3 ms 860 KB Output isn't correct
18 Correct 3 ms 888 KB Output is correct
19 Incorrect 3 ms 1144 KB Output isn't correct
20 Incorrect 3 ms 1148 KB Output isn't correct
21 Correct 2 ms 760 KB Output is correct
22 Correct 3 ms 1016 KB Output is correct
23 Incorrect 3 ms 1172 KB Output isn't correct
24 Incorrect 3 ms 1016 KB Output isn't correct
25 Incorrect 3 ms 1272 KB Output isn't correct
26 Incorrect 3 ms 1144 KB Output isn't correct
27 Correct 10 ms 3448 KB Output is correct
28 Incorrect 11 ms 3704 KB Output isn't correct
29 Incorrect 14 ms 4600 KB Output isn't correct
30 Incorrect 18 ms 5372 KB Output isn't correct
31 Correct 14 ms 4344 KB Output is correct
32 Incorrect 15 ms 4984 KB Output isn't correct
33 Incorrect 19 ms 5752 KB Output isn't correct
34 Incorrect 10 ms 3832 KB Output isn't correct
35 Incorrect 19 ms 5752 KB Output isn't correct
36 Incorrect 20 ms 5752 KB Output isn't correct
37 Incorrect 2 ms 504 KB Output isn't correct
38 Correct 575 ms 51780 KB Output is correct
39 Incorrect 2 ms 504 KB Output isn't correct
40 Incorrect 69 ms 14072 KB Output isn't correct
41 Correct 2 ms 504 KB Output is correct
42 Correct 3 ms 1272 KB Output is correct
43 Correct 591 ms 51744 KB Output is correct
44 Correct 19 ms 5752 KB Output is correct
45 Incorrect 578 ms 51704 KB Output isn't correct
46 Correct 558 ms 51796 KB Output is correct
47 Incorrect 581 ms 51832 KB Output isn't correct
48 Incorrect 596 ms 51764 KB Output isn't correct
49 Correct 597 ms 51728 KB Output is correct
50 Incorrect 562 ms 51728 KB Output isn't correct
51 Incorrect 558 ms 51924 KB Output isn't correct
52 Correct 555 ms 51580 KB Output is correct
53 Correct 556 ms 51776 KB Output is correct
54 Correct 585 ms 51732 KB Output is correct
55 Incorrect 582 ms 51704 KB Output isn't correct
56 Correct 605 ms 51816 KB Output is correct
57 Incorrect 536 ms 51704 KB Output isn't correct
58 Correct 538 ms 51832 KB Output is correct
59 Correct 538 ms 51652 KB Output is correct
60 Correct 618 ms 51404 KB Output is correct
61 Correct 597 ms 50936 KB Output is correct
62 Correct 590 ms 51040 KB Output is correct
63 Correct 601 ms 51064 KB Output is correct
64 Correct 547 ms 50936 KB Output is correct
65 Correct 551 ms 50920 KB Output is correct
66 Correct 554 ms 51064 KB Output is correct
67 Incorrect 564 ms 50992 KB Output isn't correct
68 Incorrect 565 ms 50904 KB Output isn't correct
69 Correct 541 ms 51064 KB Output is correct
70 Incorrect 326 ms 40696 KB Output isn't correct
71 Incorrect 527 ms 50972 KB Output isn't correct
72 Incorrect 543 ms 50952 KB Output isn't correct
73 Correct 537 ms 50996 KB Output is correct
74 Incorrect 536 ms 51064 KB Output isn't correct
75 Incorrect 536 ms 50936 KB Output isn't correct
76 Incorrect 535 ms 50912 KB Output isn't correct
77 Incorrect 538 ms 51064 KB Output isn't correct
78 Incorrect 537 ms 50976 KB Output isn't correct
79 Incorrect 518 ms 50936 KB Output isn't correct
80 Incorrect 578 ms 51068 KB Output isn't correct
81 Incorrect 533 ms 51056 KB Output isn't correct
82 Incorrect 540 ms 50952 KB Output isn't correct
83 Incorrect 541 ms 50552 KB Output isn't correct
84 Incorrect 536 ms 50584 KB Output isn't correct
85 Incorrect 547 ms 50492 KB Output isn't correct
86 Incorrect 572 ms 50676 KB Output isn't correct
87 Incorrect 538 ms 50644 KB Output isn't correct
88 Correct 540 ms 50648 KB Output is correct
89 Correct 549 ms 50684 KB Output is correct
90 Incorrect 334 ms 40568 KB Output isn't correct
91 Incorrect 541 ms 50572 KB Output isn't correct
92 Incorrect 566 ms 50608 KB Output isn't correct
93 Incorrect 571 ms 50620 KB Output isn't correct
94 Correct 551 ms 50568 KB Output is correct
95 Incorrect 540 ms 50608 KB Output isn't correct
96 Correct 552 ms 50636 KB Output is correct
97 Incorrect 589 ms 50496 KB Output isn't correct
98 Incorrect 536 ms 50612 KB Output isn't correct
99 Incorrect 546 ms 50552 KB Output isn't correct
100 Incorrect 572 ms 50552 KB Output isn't correct