oj.uz

Submission #957884

# Submission time Handle Problem Language Result Execution time Memory
957884 2024-04-04T12:46:27 Z gaga999 Bomb (IZhO17_bomb) C++17
0 / 100
 89 ms 600 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()
{
    freopen("bomb.in", "r", stdin);
    freopen("bomb.out", "w", stdout);
    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);
        }
        m1 = INF, m2 = INF, cr = 0;
        for (int j = m; j > 0; 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:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen("bomb.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("bomb.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%s", gd[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 416 KB Output isn't correct
2 Incorrect 73 ms 412 KB Output isn't correct
3 Incorrect 73 ms 420 KB Output isn't correct
4 Incorrect 75 ms 348 KB Output isn't correct
5 Incorrect 77 ms 344 KB Output isn't correct
6 Incorrect 76 ms 348 KB Output isn't correct
7 Incorrect 82 ms 344 KB Output isn't correct
8 Incorrect 75 ms 420 KB Output isn't correct
9 Incorrect 73 ms 420 KB Output isn't correct
10 Incorrect 77 ms 424 KB Output isn't correct
11 Incorrect 76 ms 432 KB Output isn't correct
12 Incorrect 73 ms 348 KB Output isn't correct
13 Incorrect 74 ms 348 KB Output isn't correct
14 Incorrect 81 ms 432 KB Output isn't correct
15 Incorrect 72 ms 344 KB Output isn't correct
16 Incorrect 75 ms 348 KB Output isn't correct
17 Incorrect 75 ms 420 KB Output isn't correct
18 Incorrect 81 ms 344 KB Output isn't correct
19 Incorrect 75 ms 600 KB Output isn't correct
20 Incorrect 74 ms 432 KB Output isn't correct
21 Incorrect 74 ms 344 KB Output isn't correct
22 Incorrect 89 ms 544 KB Output isn't correct
23 Incorrect 74 ms 420 KB Output isn't correct
24 Incorrect 74 ms 348 KB Output isn't correct
25 Incorrect 75 ms 428 KB Output isn't correct
26 Incorrect 73 ms 416 KB Output isn't correct
27 Incorrect 78 ms 424 KB Output isn't correct
28 Incorrect 74 ms 348 KB Output isn't correct
29 Incorrect 75 ms 344 KB Output isn't correct
30 Incorrect 74 ms 344 KB Output isn't correct
31 Incorrect 73 ms 420 KB Output isn't correct
32 Incorrect 80 ms 416 KB Output isn't correct
33 Incorrect 80 ms 348 KB Output isn't correct
34 Incorrect 75 ms 348 KB Output isn't correct
35 Incorrect 72 ms 344 KB Output isn't correct
36 Incorrect 74 ms 432 KB Output isn't correct
37 Incorrect 74 ms 596 KB Output isn't correct
38 Incorrect 72 ms 416 KB Output isn't correct
39 Incorrect 77 ms 428 KB Output isn't correct
40 Incorrect 75 ms 348 KB Output isn't correct
41 Incorrect 75 ms 344 KB Output isn't correct
42 Incorrect 85 ms 420 KB Output isn't correct
43 Incorrect 75 ms 420 KB Output isn't correct
44 Incorrect 75 ms 344 KB Output isn't correct
45 Incorrect 73 ms 344 KB Output isn't correct
46 Incorrect 76 ms 416 KB Output isn't correct
47 Incorrect 73 ms 348 KB Output isn't correct
48 Incorrect 75 ms 348 KB Output isn't correct
49 Incorrect 73 ms 420 KB Output isn't correct
50 Incorrect 75 ms 344 KB Output isn't correct
51 Incorrect 74 ms 432 KB Output isn't correct
52 Incorrect 73 ms 432 KB Output isn't correct
53 Incorrect 78 ms 500 KB Output isn't correct
54 Incorrect 75 ms 348 KB Output isn't correct
55 Incorrect 75 ms 420 KB Output isn't correct
56 Incorrect 74 ms 420 KB Output isn't correct
57 Incorrect 73 ms 344 KB Output isn't correct
58 Incorrect 79 ms 348 KB Output isn't correct
59 Incorrect 89 ms 348 KB Output isn't correct
60 Incorrect 75 ms 416 KB Output isn't correct
61 Incorrect 75 ms 428 KB Output isn't correct
62 Incorrect 73 ms 348 KB Output isn't correct
63 Incorrect 75 ms 420 KB Output isn't correct
64 Incorrect 75 ms 412 KB Output isn't correct
65 Incorrect 75 ms 344 KB Output isn't correct
66 Incorrect 73 ms 420 KB Output isn't correct
67 Incorrect 81 ms 596 KB Output isn't correct
68 Incorrect 78 ms 436 KB Output isn't correct
69 Incorrect 79 ms 420 KB Output isn't correct
70 Incorrect 80 ms 348 KB Output isn't correct
71 Incorrect 81 ms 428 KB Output isn't correct
72 Incorrect 76 ms 424 KB Output isn't correct
73 Incorrect 79 ms 420 KB Output isn't correct
74 Incorrect 78 ms 432 KB Output isn't correct
75 Incorrect 81 ms 428 KB Output isn't correct
76 Incorrect 79 ms 416 KB Output isn't correct
77 Incorrect 79 ms 428 KB Output isn't correct
78 Incorrect 81 ms 416 KB Output isn't correct
79 Incorrect 79 ms 420 KB Output isn't correct
80 Incorrect 75 ms 420 KB Output isn't correct
81 Incorrect 78 ms 428 KB Output isn't correct
82 Incorrect 73 ms 600 KB Output isn't correct
83 Incorrect 80 ms 416 KB Output isn't correct
84 Incorrect 84 ms 420 KB Output isn't correct
85 Incorrect 83 ms 420 KB Output isn't correct
86 Incorrect 78 ms 436 KB Output isn't correct
87 Incorrect 76 ms 428 KB Output isn't correct
88 Incorrect 80 ms 416 KB Output isn't correct
89 Incorrect 75 ms 348 KB Output isn't correct
90 Incorrect 75 ms 348 KB Output isn't correct
91 Incorrect 82 ms 420 KB Output isn't correct
92 Incorrect 87 ms 420 KB Output isn't correct
93 Incorrect 84 ms 420 KB Output isn't correct
94 Incorrect 80 ms 416 KB Output isn't correct
95 Incorrect 79 ms 420 KB Output isn't correct
96 Incorrect 74 ms 420 KB Output isn't correct
97 Incorrect 76 ms 344 KB Output isn't correct
98 Incorrect 75 ms 348 KB Output isn't correct
99 Incorrect 80 ms 424 KB Output isn't correct
100 Incorrect 75 ms 348 KB Output isn't correct