Submission #169913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
169913	2019-12-23T09:09:49 Z	stefdasca	Bomb (IZhO17_bomb)	C++14	61 / 100	1000 ms	63764 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];
    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);
    }
    if(n <= 450 && m <= 450)
    {
        int mxans = 0;
        for(int i = n; i >= 1; --i)
        {
            if(i * m <= mxans)
                break;
            int st = mxans / i + 1;
            int dr = m;
            int ans = 0;
            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);
        }
        for(int j = m; j >= 1; --j)
        {
            if(j * n <= mxans)
                break;
            int st = mxans / j + 1;
            int dr = n;
            int ans = 0;
            while(st <= dr)
            {
                int mid = (st + dr) / 2;
                if(chk(mid, j))
                    ans = mid, st = mid + 1;
                else
                    dr = mid - 1;
            }
            mxans = max(mxans, ans * j);
        }
        cout << mxans;
    }
    else
    {
        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

61.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	27 ms	26844 KB	Output is correct
4	Correct	27 ms	26756 KB	Output is correct
5	Correct	2 ms	424 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	3 ms	504 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	636 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	3 ms	632 KB	Output is correct
15	Correct	2 ms	632 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	6 ms	1016 KB	Output is correct
18	Correct	6 ms	1144 KB	Output is correct
19	Correct	10 ms	1400 KB	Output is correct
20	Correct	12 ms	1400 KB	Output is correct
21	Correct	6 ms	1020 KB	Output is correct
22	Correct	9 ms	1272 KB	Output is correct
23	Correct	13 ms	1584 KB	Output is correct
24	Correct	9 ms	1272 KB	Output is correct
25	Correct	16 ms	1528 KB	Output is correct
26	Correct	20 ms	1528 KB	Output is correct
27	Correct	455 ms	4260 KB	Output is correct
28	Correct	554 ms	4344 KB	Output is correct
29	Correct	882 ms	5624 KB	Output is correct
30	Execution timed out	1062 ms	6520 KB	Time limit exceeded
31	Execution timed out	1022 ms	5252 KB	Time limit exceeded
32	Execution timed out	1067 ms	6060 KB	Time limit exceeded
33	Execution timed out	1082 ms	6904 KB	Time limit exceeded
34	Correct	346 ms	4984 KB	Output is correct
35	Execution timed out	1069 ms	6904 KB	Time limit exceeded
36	Execution timed out	1077 ms	6904 KB	Time limit exceeded
37	Correct	2 ms	504 KB	Output is correct
38	Correct	16 ms	9848 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Correct	58 ms	16376 KB	Output is correct
41	Correct	2 ms	504 KB	Output is correct
42	Correct	15 ms	1496 KB	Output is correct
43	Correct	733 ms	60792 KB	Output is correct
44	Execution timed out	1059 ms	6904 KB	Time limit exceeded
45	Incorrect	433 ms	60664 KB	Output isn't correct
46	Correct	428 ms	60760 KB	Output is correct
47	Incorrect	490 ms	60792 KB	Output isn't correct
48	Correct	445 ms	60796 KB	Output is correct
49	Correct	361 ms	60792 KB	Output is correct
50	Correct	475 ms	60752 KB	Output is correct
51	Correct	471 ms	60804 KB	Output is correct
52	Correct	445 ms	60776 KB	Output is correct
53	Correct	431 ms	60756 KB	Output is correct
54	Correct	453 ms	60784 KB	Output is correct
55	Correct	438 ms	60736 KB	Output is correct
56	Correct	547 ms	63468 KB	Output is correct
57	Correct	507 ms	60372 KB	Output is correct
58	Correct	522 ms	60756 KB	Output is correct
59	Correct	484 ms	63712 KB	Output is correct
60	Correct	470 ms	63764 KB	Output is correct
61	Correct	478 ms	62200 KB	Output is correct
62	Correct	719 ms	62488 KB	Output is correct
63	Correct	743 ms	62128 KB	Output is correct
64	Correct	613 ms	62048 KB	Output is correct
65	Correct	420 ms	62048 KB	Output is correct
66	Correct	430 ms	62072 KB	Output is correct
67	Correct	464 ms	62044 KB	Output is correct
68	Correct	486 ms	62072 KB	Output is correct
69	Correct	501 ms	61788 KB	Output is correct
70	Incorrect	252 ms	50012 KB	Output isn't correct
71	Incorrect	422 ms	61432 KB	Output isn't correct
72	Incorrect	435 ms	61436 KB	Output isn't correct
73	Incorrect	418 ms	61384 KB	Output isn't correct
74	Incorrect	460 ms	61108 KB	Output isn't correct
75	Incorrect	452 ms	61112 KB	Output isn't correct
76	Incorrect	453 ms	61304 KB	Output isn't correct
77	Incorrect	481 ms	61368 KB	Output isn't correct
78	Incorrect	480 ms	61364 KB	Output isn't correct
79	Incorrect	313 ms	61436 KB	Output isn't correct
80	Incorrect	309 ms	61176 KB	Output isn't correct
81	Incorrect	360 ms	60708 KB	Output isn't correct
82	Incorrect	485 ms	60736 KB	Output isn't correct
83	Incorrect	529 ms	60708 KB	Output isn't correct
84	Incorrect	305 ms	60316 KB	Output isn't correct
85	Incorrect	427 ms	60208 KB	Output isn't correct
86	Incorrect	358 ms	59740 KB	Output isn't correct
87	Correct	414 ms	59472 KB	Output is correct
88	Incorrect	452 ms	59512 KB	Output isn't correct
89	Incorrect	407 ms	59476 KB	Output isn't correct
90	Incorrect	293 ms	48640 KB	Output isn't correct
91	Incorrect	447 ms	59608 KB	Output isn't correct
92	Incorrect	439 ms	59384 KB	Output isn't correct
93	Incorrect	394 ms	59640 KB	Output isn't correct
94	Incorrect	411 ms	59512 KB	Output isn't correct
95	Incorrect	506 ms	59484 KB	Output isn't correct
96	Incorrect	466 ms	59268 KB	Output isn't correct
97	Incorrect	359 ms	59384 KB	Output isn't correct
98	Incorrect	517 ms	59368 KB	Output isn't correct
99	Incorrect	425 ms	59456 KB	Output isn't correct
100	Incorrect	379 ms	59428 KB	Output isn't correct