답안 #957823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957823 2024-04-04T11:14:11 Z gaga999 Bomb (IZhO17_bomb) C++17
38 / 100
195 ms 62000 KB
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}

const int N = 2505;
char gd[N][N];
int up[N][N], dn[N][N], an[N];

signed main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", gd[i] + 1);
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
            if (gd[i][j] == '1')
                up[i][j] = up[i - 1][j] + 1;
        for (int i = n; i > 0; i--)
            if (gd[i][j] == '1')
                dn[i][j] = dn[i + 1][j] + 1;
    }
    init(an, INF);
    int mx = m;
    for (int i = 1; i <= n; i++)
    {
        int m1 = INF, m2 = INF, cr = 0;
        for (int j = 1; j <= m; j++)
        {
            if (gd[i][j] == '0')
            {
                m1 = m2 = INF;
                if (cr)
                    tmin(mx, cr), cr = 0;
                continue;
            }
            cr++, tmin(m1, up[i][j]), tmin(m2, dn[i][j]);
            tmin(an[cr], m1 + m2 - 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= mx; i++)
        tmax(ans, an[i] * i), tmin(an[i + 1], an[i]);
    prt(ans), putchar('\n');
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         scanf("%s", gd[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 24 ms 54276 KB Output is correct
4 Correct 7 ms 54216 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Incorrect 1 ms 2396 KB Output isn't correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Incorrect 1 ms 2396 KB Output isn't correct
13 Incorrect 1 ms 2652 KB Output isn't correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Incorrect 1 ms 2652 KB Output isn't correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Incorrect 1 ms 4700 KB Output isn't correct
20 Incorrect 1 ms 4700 KB Output isn't correct
21 Correct 1 ms 2648 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Incorrect 1 ms 4700 KB Output isn't correct
24 Incorrect 1 ms 4700 KB Output isn't correct
25 Incorrect 2 ms 4952 KB Output isn't correct
26 Incorrect 2 ms 4956 KB Output isn't correct
27 Incorrect 5 ms 11100 KB Output isn't correct
28 Incorrect 2 ms 4956 KB Output isn't correct
29 Incorrect 4 ms 10844 KB Output isn't correct
30 Incorrect 5 ms 10332 KB Output isn't correct
31 Correct 2 ms 7768 KB Output is correct
32 Incorrect 3 ms 10072 KB Output isn't correct
33 Incorrect 4 ms 10840 KB Output isn't correct
34 Incorrect 1 ms 4956 KB Output isn't correct
35 Incorrect 2 ms 7000 KB Output isn't correct
36 Incorrect 4 ms 15196 KB Output isn't correct
37 Incorrect 1 ms 2804 KB Output isn't correct
38 Correct 195 ms 61680 KB Output is correct
39 Incorrect 1 ms 2652 KB Output isn't correct
40 Incorrect 12 ms 24240 KB Output isn't correct
41 Correct 1 ms 2648 KB Output is correct
42 Correct 1 ms 3272 KB Output is correct
43 Correct 146 ms 59592 KB Output is correct
44 Correct 4 ms 14172 KB Output is correct
45 Incorrect 124 ms 61372 KB Output isn't correct
46 Correct 139 ms 61612 KB Output is correct
47 Incorrect 116 ms 61520 KB Output isn't correct
48 Correct 114 ms 61744 KB Output is correct
49 Incorrect 167 ms 61520 KB Output isn't correct
50 Correct 111 ms 61748 KB Output is correct
51 Correct 124 ms 61700 KB Output is correct
52 Correct 113 ms 61612 KB Output is correct
53 Correct 123 ms 61232 KB Output is correct
54 Correct 92 ms 53588 KB Output is correct
55 Incorrect 97 ms 50996 KB Output isn't correct
56 Correct 157 ms 61520 KB Output is correct
57 Incorrect 75 ms 48260 KB Output isn't correct
58 Correct 76 ms 51184 KB Output is correct
59 Correct 74 ms 50788 KB Output is correct
60 Incorrect 95 ms 60592 KB Output isn't correct
61 Incorrect 178 ms 61548 KB Output isn't correct
62 Incorrect 157 ms 62000 KB Output isn't correct
63 Incorrect 163 ms 61640 KB Output isn't correct
64 Incorrect 72 ms 61012 KB Output isn't correct
65 Correct 105 ms 61268 KB Output is correct
66 Correct 104 ms 61100 KB Output is correct
67 Correct 120 ms 61740 KB Output is correct
68 Correct 120 ms 61744 KB Output is correct
69 Correct 72 ms 48212 KB Output is correct
70 Incorrect 32 ms 24912 KB Output isn't correct
71 Incorrect 48 ms 47516 KB Output isn't correct
72 Incorrect 66 ms 48980 KB Output isn't correct
73 Correct 64 ms 49324 KB Output is correct
74 Incorrect 67 ms 53300 KB Output isn't correct
75 Incorrect 64 ms 56260 KB Output isn't correct
76 Incorrect 73 ms 57428 KB Output isn't correct
77 Incorrect 60 ms 57472 KB Output isn't correct
78 Incorrect 73 ms 57940 KB Output isn't correct
79 Incorrect 44 ms 23344 KB Output isn't correct
80 Incorrect 36 ms 27220 KB Output isn't correct
81 Incorrect 52 ms 27212 KB Output isn't correct
82 Incorrect 77 ms 58920 KB Output isn't correct
83 Incorrect 69 ms 59680 KB Output isn't correct
84 Incorrect 34 ms 16816 KB Output isn't correct
85 Incorrect 68 ms 58968 KB Output isn't correct
86 Incorrect 155 ms 61008 KB Output isn't correct
87 Incorrect 67 ms 58860 KB Output isn't correct
88 Correct 80 ms 57952 KB Output is correct
89 Correct 97 ms 59412 KB Output is correct
90 Incorrect 37 ms 48636 KB Output isn't correct
91 Incorrect 87 ms 59268 KB Output isn't correct
92 Incorrect 81 ms 57940 KB Output isn't correct
93 Incorrect 146 ms 60500 KB Output isn't correct
94 Correct 96 ms 58764 KB Output is correct
95 Incorrect 96 ms 59728 KB Output isn't correct
96 Correct 70 ms 58928 KB Output is correct
97 Incorrect 156 ms 60844 KB Output isn't correct
98 Incorrect 78 ms 59308 KB Output isn't correct
99 Incorrect 95 ms 59488 KB Output isn't correct
100 Incorrect 141 ms 60160 KB Output isn't correct