답안 #94302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94302	2019-01-17T12:27:41 Z	Kastanda	Bomb (IZhO17_bomb)	C++11	29 / 100	338 ms	60920 KB

bomb

#include<bits/stdc++.h>
using namespace std;
const int N = 2505;
int n, m, Mnx, Mny, R[N], up[N][N], dn[N][N];
int qu[N], F[N];
char A[N][N];
inline int Calc(int lenx)
{
    if (lenx > Mnx)
        return 0;

    int Mn = n;
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = 0;
        for (int j = 1; j <= m; j++)
        {
            while (r - l && dn[i][j] <= dn[i][qu[r-1]])
                r --;
            qu[r ++] = j;
            if (qu[l] <= j - lenx)
                l ++;
            F[j - lenx + 1] = dn[i][qu[l]] - 1;
        }
        l = r = 0;
        for (int j = 1; j <= m; j++)
        {
            while (r - l && up[i][j] >= up[i][qu[r-1]])
                r --;
            qu[r ++] = j;
            if (qu[l] <= j - lenx)
                l ++;
            F[j - lenx + 1] -= up[i][qu[l]];
        }
        l = r = 0;
        for (int j = 1; j <= m - lenx + 1; j++)
        {
            F[j] = max(F[j], 0);
            while (r - l && F[j] >= F[qu[r-1]])
                r --;
            qu[r ++] = j;
            while (qu[l] <= j - lenx)
                l ++;
            if (A[i][j] == '1')
                Mn = min(Mn, F[qu[l]]);
        }
    }
    return (Mn);
}
inline void Init()
{
    Mnx = m; Mny = n;

    for (int i = 1; i <= n; i++)
    {
        int last = 0;
        for (int j = 1; j <= m; j++)
            if (A[i][j] == '0')
            {
                if (last != j - 1)
                    Mnx = min(Mnx, j - last - 1);
                last = j;
            }
        if (last != m)
            Mnx = min(Mnx, m - last);
    }

    for (int i = 1; i <= m; i++)
    {
        int last = 0;
        for (int j = 1; j <= n; j++)
            if (A[j][i] == '0')
            {
                if (last != j - 1)
                    Mny = min(Mny, j - last - 1);
                last = j;
            }
        if (last != n)
            Mny = min(Mny, n - last);
    }
}
void Solve(int l = 1, int r = Mnx)
{
    if (r - l + 1 <= 2)
        return ;
    if (R[l] == R[r])
    {
        for (int i = l + 1; i < r; i++)
            R[i] = R[l];
        return ;
    }
    int md = (l + r) >> 1;
    R[md] = Calc(md);
    Solve(l, md);
    Solve(md, r);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", &A[i][1]);
    Init();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            up[i][j] = i - 1;
            if (A[i - 1][j] == '1')
                up[i][j] = up[i - 1][j];
        }
    for (int i = n; i; i--)
        for (int j = 1; j <= m; j++)
        {
            dn[i][j] = i + 1;
            if (A[i + 1][j] == '1')
                dn[i][j] = dn[i + 1][j];

            if (A[i][j] == '0')
                dn[i][j] = 0, up[i][j] = n + 1;
        }
    R[1] = Calc(1);
    R[Mnx] = Calc(Mnx);
    int Mx_s = 0;
    for (int i = 1; i <= Mnx; i++)
        Mx_s = max(Mx_s, i * R[i]);
    return !printf("%d", Mx_s);
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &A[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

29.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	20 ms	26488 KB	Output is correct
4	Correct	18 ms	26488 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	508 KB	Output isn't correct
10	Incorrect	2 ms	504 KB	Output isn't correct
11	Incorrect	2 ms	632 KB	Output isn't correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Incorrect	2 ms	504 KB	Output isn't correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	3 ms	1016 KB	Output is correct
18	Incorrect	2 ms	1144 KB	Output isn't correct
19	Incorrect	2 ms	1400 KB	Output isn't correct
20	Incorrect	3 ms	1400 KB	Output isn't correct
21	Incorrect	2 ms	1016 KB	Output isn't correct
22	Incorrect	2 ms	1272 KB	Output isn't correct
23	Incorrect	17 ms	1528 KB	Output isn't correct
24	Incorrect	2 ms	1272 KB	Output isn't correct
25	Incorrect	3 ms	1528 KB	Output isn't correct
26	Correct	3 ms	1400 KB	Output is correct
27	Correct	6 ms	4088 KB	Output is correct
28	Incorrect	8 ms	4216 KB	Output isn't correct
29	Incorrect	10 ms	5468 KB	Output isn't correct
30	Incorrect	11 ms	6392 KB	Output isn't correct
31	Incorrect	9 ms	5112 KB	Output isn't correct
32	Incorrect	9 ms	5904 KB	Output isn't correct
33	Incorrect	12 ms	6904 KB	Output isn't correct
34	Incorrect	7 ms	4728 KB	Output isn't correct
35	Incorrect	12 ms	6776 KB	Output isn't correct
36	Correct	13 ms	6696 KB	Output is correct
37	Correct	2 ms	504 KB	Output is correct
38	Correct	205 ms	60380 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Correct	35 ms	16120 KB	Output is correct
41	Incorrect	2 ms	504 KB	Output isn't correct
42	Incorrect	3 ms	1400 KB	Output isn't correct
43	Correct	255 ms	60416 KB	Output is correct
44	Incorrect	12 ms	6776 KB	Output isn't correct
45	Incorrect	230 ms	60396 KB	Output isn't correct
46	Correct	282 ms	60280 KB	Output is correct
47	Incorrect	228 ms	60452 KB	Output isn't correct
48	Incorrect	235 ms	60408 KB	Output isn't correct
49	Correct	226 ms	60492 KB	Output is correct
50	Incorrect	226 ms	60280 KB	Output isn't correct
51	Incorrect	226 ms	60380 KB	Output isn't correct
52	Incorrect	223 ms	60380 KB	Output isn't correct
53	Incorrect	236 ms	60408 KB	Output isn't correct
54	Incorrect	224 ms	60408 KB	Output isn't correct
55	Incorrect	257 ms	60304 KB	Output isn't correct
56	Correct	248 ms	60368 KB	Output is correct
57	Incorrect	338 ms	60412 KB	Output isn't correct
58	Incorrect	225 ms	60284 KB	Output isn't correct
59	Incorrect	224 ms	60280 KB	Output isn't correct
60	Correct	212 ms	60280 KB	Output is correct
61	Correct	240 ms	60420 KB	Output is correct
62	Correct	213 ms	60408 KB	Output is correct
63	Correct	201 ms	60548 KB	Output is correct
64	Correct	222 ms	60408 KB	Output is correct
65	Incorrect	217 ms	60408 KB	Output isn't correct
66	Incorrect	208 ms	60540 KB	Output isn't correct
67	Incorrect	222 ms	60632 KB	Output isn't correct
68	Incorrect	245 ms	60580 KB	Output isn't correct
69	Incorrect	244 ms	60552 KB	Output isn't correct
70	Incorrect	170 ms	48248 KB	Output isn't correct
71	Incorrect	254 ms	60408 KB	Output isn't correct
72	Incorrect	232 ms	60536 KB	Output isn't correct
73	Incorrect	232 ms	60508 KB	Output isn't correct
74	Incorrect	244 ms	60536 KB	Output isn't correct
75	Incorrect	226 ms	60536 KB	Output isn't correct
76	Incorrect	224 ms	60668 KB	Output isn't correct
77	Incorrect	219 ms	60664 KB	Output isn't correct
78	Incorrect	238 ms	60664 KB	Output isn't correct
79	Incorrect	235 ms	60664 KB	Output isn't correct
80	Incorrect	239 ms	60800 KB	Output isn't correct
81	Incorrect	246 ms	60920 KB	Output isn't correct
82	Incorrect	234 ms	60920 KB	Output isn't correct
83	Incorrect	224 ms	60792 KB	Output isn't correct
84	Incorrect	238 ms	60792 KB	Output isn't correct
85	Incorrect	216 ms	60856 KB	Output isn't correct
86	Incorrect	219 ms	60664 KB	Output isn't correct
87	Correct	221 ms	60664 KB	Output is correct
88	Incorrect	218 ms	60536 KB	Output isn't correct
89	Incorrect	219 ms	60772 KB	Output isn't correct
90	Incorrect	145 ms	48248 KB	Output isn't correct
91	Incorrect	221 ms	60792 KB	Output isn't correct
92	Incorrect	215 ms	60792 KB	Output isn't correct
93	Incorrect	206 ms	60616 KB	Output isn't correct
94	Incorrect	243 ms	60636 KB	Output isn't correct
95	Incorrect	228 ms	60792 KB	Output isn't correct
96	Incorrect	242 ms	60920 KB	Output isn't correct
97	Incorrect	223 ms	60768 KB	Output isn't correct
98	Incorrect	246 ms	60636 KB	Output isn't correct
99	Incorrect	236 ms	60664 KB	Output isn't correct
100	Incorrect	227 ms	60688 KB	Output isn't correct