답안 #169921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169921	2019-12-23T09:22:05 Z	stefdasca	Bomb (IZhO17_bomb)	C++14	68 / 100	784 ms	59000 KB

bomb

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
    long long a = rng();
    return a;
}
char c[2600][2600];
int n, m, mars[2600][2600], sp[2600][2600];
int sum(int xa, int ya, int xb, int yb)
{
    return sp[xb][yb] - sp[xa - 1][yb] - sp[xb][ya - 1] + sp[xa - 1][ya - 1];
}
bool chk(int i, int j)
{
    for(int q = i; q <= n; ++q)
        for(int p = j; p <= m; ++p)
        {
            if(sp[q][p] - sp[q - i][p] - sp[q][p - j] + sp[q - i][p - j] == i * j)
            {
                mars[q - i + 1][p - j + 1]++;
                mars[q + 1][p - j + 1]--;
                mars[q - i + 1][p + 1]--;
                mars[q + 1][p + 1]++;
            }
        }
    bool ok = 1;
    for(int q = 1; q <= n; ++q)
        for(int p = 1; p <= m; ++p)
        {
            mars[q][p] = mars[q][p] + mars[q-1][p] + mars[q][p-1] - mars[q-1][p-1];
            if(c[q][p] == '1' && !mars[q][p])
            {
                ok = 0;
                p = m+1;
                q = n+1;
            }
        }
    for(int q = 1; q <= n; ++q)
        for(int p = 1; p <= m; ++p)
            mars[q][p] = 0;
    return ok;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> (c[i] + 1);
    int xx = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            xx += (c[i][j] == '0');
    if(!xx)
    {
        cout << n*m;
        return 0;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            sp[i][j] = (c[i][j] - '0') + sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1];
    if(n <= 450 && m <= 450)
    {
        int mxans = 0;
        for(int i = n; i >= 1; --i)
        {
            int st = mxans / i + 1;
            int dr = m;
            if(st > dr)
                break;
            int ans = 0;
            if(chk(i, st))
                while(st <= dr)
                {
                    int mid = (st + dr) / 2;
                    if(chk(i, mid))
                        ans = mid, st = mid + 1;
                    else
                        dr = mid - 1;
                }
            mxans = max(mxans, i * ans);
        }
        cout << mxans;
    }
    else
    {
        int mnx = m, mny = n;
        for(int i = 1; i <= n; ++i)
        {
            int str = 0;
            for(int j = 1; j <= m; ++j)
            {
                if(c[i][j] == '1')
                    ++str;
                else
                {
                    if(str)
                        mnx = min(mnx, str);
                    str = 0;
                }
            }
            if(str)
                mnx = min(mnx, str);
        }
        for(int j = 1; j <= m; ++j)
        {
            int str = 0;
            for(int i = 1; i <= n; ++i)
            {
                if(c[i][j] == '1')
                    ++str;
                else
                {
                    if(str)
                        mny = min(mny, str);
                    str = 0;
                }
            }
            if(str)
                mny = min(mny, str);
        }
        int mxans = 0;
        // mnx * some number
        int st = 1;
        int dr = mny;
        int ans = 1;
        while(st <= dr)
        {
            int mid = (st + dr) / 2;
            if(chk(mid, mnx))
                ans = mid, st = mid + 1;
            else
                dr = mid - 1;
        }
        mxans = max(mxans, ans * mnx);
        st = 1;
        dr = mnx;
        ans = 1;
        while(st <= dr)
        {
            int mid = (st + dr) / 2;
            if(chk(mny, mid))
                ans = mid, st = mid + 1;
            else
                dr = mid - 1;
        }
        mxans = max(mxans, mny * ans);
        cout << mxans;
    }
    return 0;
}

Compilation message

bomb.cpp: In function 'bool chk(int, int)':
bomb.cpp:70:26: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
         for(int p = 1; p <= m; ++p)
                        ~~^~~~

Subtask #1

68.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	632 KB	Output is correct
3	Correct	28 ms	26872 KB	Output is correct
4	Correct	27 ms	26764 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	Correct	2 ms	504 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	2 ms	548 KB	Output is correct
11	Correct	2 ms	548 KB	Output is 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	Correct	2 ms	508 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	3 ms	1016 KB	Output is correct
18	Correct	3 ms	1144 KB	Output is correct
19	Correct	4 ms	1400 KB	Output is correct
20	Correct	4 ms	1400 KB	Output is correct
21	Correct	3 ms	988 KB	Output is correct
22	Correct	4 ms	1272 KB	Output is correct
23	Correct	5 ms	1528 KB	Output is correct
24	Correct	4 ms	1272 KB	Output is correct
25	Correct	5 ms	1656 KB	Output is correct
26	Correct	5 ms	1528 KB	Output is correct
27	Correct	51 ms	4220 KB	Output is correct
28	Correct	45 ms	4472 KB	Output is correct
29	Correct	119 ms	5752 KB	Output is correct
30	Correct	115 ms	6520 KB	Output is correct
31	Correct	72 ms	5256 KB	Output is correct
32	Correct	95 ms	6056 KB	Output is correct
33	Correct	140 ms	6904 KB	Output is correct
34	Correct	39 ms	4856 KB	Output is correct
35	Correct	107 ms	6904 KB	Output is correct
36	Correct	177 ms	6908 KB	Output is correct
37	Correct	2 ms	632 KB	Output is correct
38	Correct	17 ms	7928 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Correct	61 ms	15988 KB	Output is correct
41	Correct	2 ms	504 KB	Output is correct
42	Correct	7 ms	1656 KB	Output is correct
43	Correct	784 ms	58804 KB	Output is correct
44	Correct	288 ms	6904 KB	Output is correct
45	Incorrect	432 ms	59000 KB	Output isn't correct
46	Correct	434 ms	58864 KB	Output is correct
47	Incorrect	451 ms	58940 KB	Output isn't correct
48	Correct	438 ms	58816 KB	Output is correct
49	Correct	367 ms	58872 KB	Output is correct
50	Correct	472 ms	58964 KB	Output is correct
51	Correct	470 ms	58996 KB	Output is correct
52	Correct	454 ms	58804 KB	Output is correct
53	Correct	424 ms	58828 KB	Output is correct
54	Correct	442 ms	59000 KB	Output is correct
55	Correct	424 ms	58872 KB	Output is correct
56	Correct	563 ms	58232 KB	Output is correct
57	Correct	531 ms	58872 KB	Output is correct
58	Correct	535 ms	58616 KB	Output is correct
59	Correct	486 ms	58276 KB	Output is correct
60	Correct	461 ms	58284 KB	Output is correct
61	Correct	477 ms	58284 KB	Output is correct
62	Correct	726 ms	58364 KB	Output is correct
63	Correct	735 ms	58616 KB	Output is correct
64	Correct	617 ms	58360 KB	Output is correct
65	Correct	398 ms	58284 KB	Output is correct
66	Correct	430 ms	58332 KB	Output is correct
67	Correct	437 ms	58360 KB	Output is correct
68	Correct	514 ms	58360 KB	Output is correct
69	Correct	483 ms	58364 KB	Output is correct
70	Incorrect	260 ms	46968 KB	Output isn't correct
71	Incorrect	471 ms	58488 KB	Output isn't correct
72	Incorrect	475 ms	58504 KB	Output isn't correct
73	Incorrect	417 ms	58488 KB	Output isn't correct
74	Incorrect	441 ms	58572 KB	Output isn't correct
75	Incorrect	454 ms	58616 KB	Output isn't correct
76	Incorrect	450 ms	58488 KB	Output isn't correct
77	Incorrect	495 ms	58560 KB	Output isn't correct
78	Incorrect	479 ms	58588 KB	Output isn't correct
79	Incorrect	314 ms	58472 KB	Output isn't correct
80	Incorrect	306 ms	58440 KB	Output isn't correct
81	Incorrect	355 ms	58488 KB	Output isn't correct
82	Incorrect	479 ms	58616 KB	Output isn't correct
83	Incorrect	491 ms	58616 KB	Output isn't correct
84	Incorrect	282 ms	58616 KB	Output isn't correct
85	Incorrect	431 ms	58660 KB	Output isn't correct
86	Incorrect	356 ms	58616 KB	Output isn't correct
87	Correct	416 ms	58616 KB	Output is correct
88	Incorrect	453 ms	58872 KB	Output isn't correct
89	Incorrect	468 ms	58616 KB	Output isn't correct
90	Incorrect	288 ms	47036 KB	Output isn't correct
91	Incorrect	444 ms	58748 KB	Output isn't correct
92	Incorrect	452 ms	58744 KB	Output isn't correct
93	Incorrect	383 ms	58680 KB	Output isn't correct
94	Incorrect	417 ms	58776 KB	Output isn't correct
95	Incorrect	527 ms	58744 KB	Output isn't correct
96	Incorrect	476 ms	58768 KB	Output isn't correct
97	Incorrect	356 ms	58712 KB	Output isn't correct
98	Incorrect	533 ms	58744 KB	Output isn't correct
99	Incorrect	455 ms	58872 KB	Output isn't correct
100	Incorrect	399 ms	58772 KB	Output isn't correct