답안 #169906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169906	2019-12-23T08:47:52 Z	stefdasca	Bomb (IZhO17_bomb)	C++14	46 / 100	1000 ms	8312 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 mars[2600][2600], sp[2600][2600];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    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;
    }
    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)
    {
        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 mxans = 0;
        for(int i = mny; i >= 1; --i)
            for(int j = mnx; j >= 1; --j)
            {
                if(i*j <= mxans)
                    continue;
                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;
                if(ok)
                    mxans = max(mxans, i*j);
            }
        cout << mxans;
    }
    else
        cout << mnx * mny;
    return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:131:38: 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)
                                    ~~^~~~
bomb.cpp:131:38: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

Subtask #1

46.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	7 ms	6776 KB	Output is correct
4	Correct	7 ms	6648 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	504 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	516 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	504 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	7 ms	1400 KB	Output is correct
20	Correct	7 ms	1400 KB	Output is correct
21	Correct	3 ms	1016 KB	Output is correct
22	Correct	3 ms	1144 KB	Output is correct
23	Correct	10 ms	1528 KB	Output is correct
24	Correct	6 ms	1312 KB	Output is correct
25	Correct	24 ms	1432 KB	Output is correct
26	Correct	3 ms	1528 KB	Output is correct
27	Correct	7 ms	4216 KB	Output is correct
28	Correct	13 ms	4344 KB	Output is correct
29	Correct	396 ms	5724 KB	Output is correct
30	Execution timed out	1070 ms	6520 KB	Time limit exceeded
31	Execution timed out	1086 ms	5240 KB	Time limit exceeded
32	Execution timed out	1040 ms	6008 KB	Time limit exceeded
33	Execution timed out	1060 ms	6904 KB	Time limit exceeded
34	Correct	11 ms	4856 KB	Output is correct
35	Correct	823 ms	7032 KB	Output is correct
36	Correct	10 ms	6904 KB	Output is correct
37	Correct	2 ms	552 KB	Output is correct
38	Correct	16 ms	7672 KB	Output is correct
39	Correct	2 ms	504 KB	Output is correct
40	Incorrect	7 ms	3192 KB	Output isn't correct
41	Correct	2 ms	504 KB	Output is correct
42	Correct	20 ms	1580 KB	Output is correct
43	Correct	42 ms	7672 KB	Output is correct
44	Execution timed out	1077 ms	6904 KB	Time limit exceeded
45	Incorrect	41 ms	7544 KB	Output isn't correct
46	Correct	49 ms	7772 KB	Output is correct
47	Incorrect	42 ms	7676 KB	Output isn't correct
48	Incorrect	42 ms	7672 KB	Output isn't correct
49	Correct	44 ms	7800 KB	Output is correct
50	Incorrect	40 ms	7752 KB	Output isn't correct
51	Incorrect	41 ms	7804 KB	Output isn't correct
52	Incorrect	41 ms	7756 KB	Output isn't correct
53	Incorrect	42 ms	7928 KB	Output isn't correct
54	Incorrect	40 ms	7928 KB	Output isn't correct
55	Incorrect	39 ms	7800 KB	Output isn't correct
56	Correct	45 ms	8184 KB	Output is correct
57	Incorrect	39 ms	7816 KB	Output isn't correct
58	Incorrect	40 ms	7932 KB	Output isn't correct
59	Incorrect	40 ms	7920 KB	Output isn't correct
60	Correct	40 ms	7932 KB	Output is correct
61	Correct	42 ms	7840 KB	Output is correct
62	Correct	42 ms	7800 KB	Output is correct
63	Correct	43 ms	7820 KB	Output is correct
64	Correct	39 ms	8060 KB	Output is correct
65	Incorrect	40 ms	7800 KB	Output isn't correct
66	Incorrect	39 ms	7672 KB	Output isn't correct
67	Incorrect	41 ms	8124 KB	Output isn't correct
68	Incorrect	42 ms	8056 KB	Output isn't correct
69	Incorrect	40 ms	8312 KB	Output isn't correct
70	Incorrect	25 ms	6392 KB	Output isn't correct
71	Incorrect	37 ms	7800 KB	Output isn't correct
72	Incorrect	40 ms	7800 KB	Output isn't correct
73	Incorrect	39 ms	7928 KB	Output isn't correct
74	Incorrect	39 ms	7928 KB	Output isn't correct
75	Incorrect	39 ms	7672 KB	Output isn't correct
76	Incorrect	40 ms	7928 KB	Output isn't correct
77	Incorrect	41 ms	7672 KB	Output isn't correct
78	Incorrect	39 ms	7884 KB	Output isn't correct
79	Incorrect	39 ms	7672 KB	Output isn't correct
80	Incorrect	39 ms	8184 KB	Output isn't correct
81	Incorrect	40 ms	7672 KB	Output isn't correct
82	Incorrect	41 ms	8080 KB	Output isn't correct
83	Incorrect	40 ms	7672 KB	Output isn't correct
84	Incorrect	39 ms	8056 KB	Output isn't correct
85	Incorrect	41 ms	7800 KB	Output isn't correct
86	Incorrect	48 ms	7800 KB	Output isn't correct
87	Incorrect	40 ms	7800 KB	Output isn't correct
88	Incorrect	40 ms	7672 KB	Output isn't correct
89	Incorrect	41 ms	6904 KB	Output isn't correct
90	Incorrect	26 ms	6392 KB	Output isn't correct
91	Incorrect	35 ms	7544 KB	Output isn't correct
92	Incorrect	41 ms	8056 KB	Output isn't correct
93	Incorrect	42 ms	7416 KB	Output isn't correct
94	Incorrect	41 ms	8056 KB	Output isn't correct
95	Incorrect	40 ms	8056 KB	Output isn't correct
96	Incorrect	41 ms	8056 KB	Output isn't correct
97	Incorrect	42 ms	7416 KB	Output isn't correct
98	Incorrect	39 ms	8068 KB	Output isn't correct
99	Incorrect	40 ms	8184 KB	Output isn't correct
100	Incorrect	41 ms	7928 KB	Output isn't correct