답안 #957851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957851 2024-04-04T12:12:32 Z gaga999 Bomb (IZhO17_bomb) C++17
48 / 100
196 ms 59288 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);
            tmin(an[1], up[i][j] + dn[i][j] - 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 2492 KB Output is correct
3 Correct 19 ms 54364 KB Output is correct
4 Correct 8 ms 54360 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Incorrect 1 ms 2496 KB Output isn't correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2496 KB Output isn't correct
9 Incorrect 1 ms 2392 KB Output isn't correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Incorrect 1 ms 2396 KB Output isn't correct
13 Correct 1 ms 2396 KB Output is 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 2396 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Incorrect 1 ms 4696 KB Output isn't correct
24 Incorrect 1 ms 4804 KB Output isn't correct
25 Incorrect 1 ms 4956 KB Output isn't correct
26 Correct 1 ms 4956 KB Output is correct
27 Correct 3 ms 11276 KB Output is correct
28 Incorrect 2 ms 4956 KB Output isn't correct
29 Incorrect 4 ms 10700 KB Output isn't correct
30 Incorrect 3 ms 10332 KB Output isn't correct
31 Correct 2 ms 7768 KB Output is correct
32 Incorrect 3 ms 10076 KB Output isn't correct
33 Incorrect 4 ms 10844 KB Output isn't correct
34 Incorrect 1 ms 4956 KB Output isn't correct
35 Incorrect 2 ms 7004 KB Output isn't correct
36 Incorrect 4 ms 15196 KB Output isn't correct
37 Incorrect 1 ms 2652 KB Output isn't correct
38 Correct 171 ms 59036 KB Output is correct
39 Incorrect 1 ms 2652 KB Output isn't correct
40 Incorrect 14 ms 23836 KB Output isn't correct
41 Correct 1 ms 2848 KB Output is correct
42 Correct 1 ms 3164 KB Output is correct
43 Correct 150 ms 56732 KB Output is correct
44 Correct 5 ms 14172 KB Output is correct
45 Incorrect 126 ms 58708 KB Output isn't correct
46 Correct 124 ms 58708 KB Output is correct
47 Incorrect 143 ms 58384 KB Output isn't correct
48 Correct 126 ms 58712 KB Output is correct
49 Correct 196 ms 58804 KB Output is correct
50 Correct 129 ms 58704 KB Output is correct
51 Correct 125 ms 58708 KB Output is correct
52 Correct 113 ms 59288 KB Output is correct
53 Correct 110 ms 58460 KB Output is correct
54 Correct 96 ms 50768 KB Output is correct
55 Incorrect 91 ms 48148 KB Output isn't correct
56 Correct 187 ms 59148 KB Output is correct
57 Incorrect 78 ms 45692 KB Output isn't correct
58 Correct 89 ms 48468 KB Output is correct
59 Correct 89 ms 48096 KB Output is correct
60 Correct 118 ms 57812 KB Output is correct
61 Correct 187 ms 58776 KB Output is correct
62 Correct 184 ms 58940 KB Output is correct
63 Correct 189 ms 59144 KB Output is correct
64 Correct 78 ms 58112 KB Output is correct
65 Correct 120 ms 58332 KB Output is correct
66 Correct 131 ms 58452 KB Output is correct
67 Correct 136 ms 58844 KB Output is correct
68 Correct 140 ms 58804 KB Output is correct
69 Correct 79 ms 45576 KB Output is correct
70 Incorrect 38 ms 23352 KB Output isn't correct
71 Incorrect 64 ms 44724 KB Output isn't correct
72 Incorrect 74 ms 46216 KB Output isn't correct
73 Correct 71 ms 46416 KB Output is correct
74 Incorrect 74 ms 50512 KB Output isn't correct
75 Incorrect 76 ms 53844 KB Output isn't correct
76 Incorrect 77 ms 54604 KB Output isn't correct
77 Incorrect 83 ms 54868 KB Output isn't correct
78 Incorrect 83 ms 54968 KB Output isn't correct
79 Incorrect 35 ms 20304 KB Output isn't correct
80 Incorrect 35 ms 24432 KB Output isn't correct
81 Incorrect 37 ms 24400 KB Output isn't correct
82 Incorrect 71 ms 56148 KB Output isn't correct
83 Incorrect 68 ms 56400 KB Output isn't correct
84 Incorrect 32 ms 13976 KB Output isn't correct
85 Incorrect 82 ms 56160 KB Output isn't correct
86 Incorrect 173 ms 58192 KB Output isn't correct
87 Incorrect 75 ms 56196 KB Output isn't correct
88 Correct 92 ms 55124 KB Output is correct
89 Correct 111 ms 56656 KB Output is correct
90 Incorrect 41 ms 46676 KB Output isn't correct
91 Incorrect 92 ms 56340 KB Output isn't correct
92 Incorrect 114 ms 55040 KB Output isn't correct
93 Incorrect 170 ms 57684 KB Output isn't correct
94 Correct 111 ms 55896 KB Output is correct
95 Incorrect 85 ms 56924 KB Output isn't correct
96 Correct 88 ms 56028 KB Output is correct
97 Incorrect 163 ms 58224 KB Output isn't correct
98 Incorrect 88 ms 56472 KB Output isn't correct
99 Incorrect 101 ms 56660 KB Output isn't correct
100 Incorrect 163 ms 57424 KB Output isn't correct