답안 #169893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169893	2019-12-23T08:28:17 Z	stefdasca	Bomb (IZhO17_bomb)	C++14	42 / 100	83 ms	9668 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;
    }
    if(n <= 100 && m <= 100)
    {
        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 = n; i >= 1; --i)
            for(int j = m; 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
    {
        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);
        }
        cout << mnx * mny << '\n';
    }
    return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:96: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)
                                    ~~^~~~

Subtask #1

42.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	7 ms	6648 KB	Output is correct
4	Correct	7 ms	6776 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	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	3 ms	556 KB	Output is correct
11	Correct	2 ms	632 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	504 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	16 ms	1144 KB	Output is correct
18	Correct	17 ms	1144 KB	Output is correct
19	Correct	39 ms	1400 KB	Output is correct
20	Correct	45 ms	1400 KB	Output is correct
21	Correct	17 ms	888 KB	Output is correct
22	Correct	33 ms	1272 KB	Output is correct
23	Correct	55 ms	1628 KB	Output is correct
24	Correct	28 ms	1400 KB	Output is correct
25	Correct	66 ms	1552 KB	Output is correct
26	Correct	79 ms	1528 KB	Output is correct
27	Correct	3 ms	1144 KB	Output is correct
28	Incorrect	3 ms	1272 KB	Output isn't correct
29	Incorrect	3 ms	1400 KB	Output isn't correct
30	Incorrect	4 ms	1656 KB	Output isn't correct
31	Incorrect	3 ms	1400 KB	Output isn't correct
32	Incorrect	3 ms	1528 KB	Output isn't correct
33	Incorrect	4 ms	1656 KB	Output isn't correct
34	Incorrect	3 ms	1272 KB	Output isn't correct
35	Incorrect	4 ms	1656 KB	Output isn't correct
36	Correct	4 ms	1656 KB	Output is correct
37	Correct	2 ms	504 KB	Output is correct
38	Correct	16 ms	7544 KB	Output is correct
39	Correct	2 ms	632 KB	Output is correct
40	Incorrect	7 ms	3064 KB	Output isn't correct
41	Correct	2 ms	632 KB	Output is correct
42	Correct	54 ms	1528 KB	Output is correct
43	Correct	60 ms	7672 KB	Output is correct
44	Incorrect	4 ms	1828 KB	Output isn't correct
45	Incorrect	46 ms	7544 KB	Output isn't correct
46	Correct	56 ms	7672 KB	Output is correct
47	Incorrect	47 ms	7544 KB	Output isn't correct
48	Incorrect	83 ms	7548 KB	Output isn't correct
49	Correct	47 ms	8592 KB	Output is correct
50	Incorrect	41 ms	7800 KB	Output isn't correct
51	Incorrect	41 ms	8440 KB	Output isn't correct
52	Incorrect	57 ms	8184 KB	Output isn't correct
53	Incorrect	45 ms	8568 KB	Output isn't correct
54	Incorrect	41 ms	8440 KB	Output isn't correct
55	Incorrect	39 ms	8568 KB	Output isn't correct
56	Correct	44 ms	8436 KB	Output is correct
57	Incorrect	39 ms	8660 KB	Output isn't correct
58	Incorrect	39 ms	8444 KB	Output isn't correct
59	Incorrect	40 ms	8572 KB	Output isn't correct
60	Correct	51 ms	8440 KB	Output is correct
61	Correct	43 ms	8696 KB	Output is correct
62	Correct	43 ms	8596 KB	Output is correct
63	Correct	43 ms	9668 KB	Output is correct
64	Correct	40 ms	8568 KB	Output is correct
65	Incorrect	44 ms	8696 KB	Output isn't correct
66	Incorrect	41 ms	7544 KB	Output isn't correct
67	Incorrect	41 ms	9468 KB	Output isn't correct
68	Incorrect	47 ms	8696 KB	Output isn't correct
69	Incorrect	40 ms	9592 KB	Output isn't correct
70	Incorrect	24 ms	6264 KB	Output isn't correct
71	Incorrect	44 ms	7544 KB	Output isn't correct
72	Incorrect	42 ms	9464 KB	Output isn't correct
73	Incorrect	41 ms	9208 KB	Output isn't correct
74	Incorrect	41 ms	8568 KB	Output isn't correct
75	Incorrect	47 ms	9520 KB	Output isn't correct
76	Incorrect	46 ms	9336 KB	Output isn't correct
77	Incorrect	43 ms	7800 KB	Output isn't correct
78	Incorrect	40 ms	9208 KB	Output isn't correct
79	Incorrect	38 ms	9208 KB	Output isn't correct
80	Incorrect	37 ms	9592 KB	Output isn't correct
81	Incorrect	39 ms	7544 KB	Output isn't correct
82	Incorrect	41 ms	8312 KB	Output isn't correct
83	Incorrect	40 ms	8696 KB	Output isn't correct
84	Incorrect	39 ms	9208 KB	Output isn't correct
85	Incorrect	45 ms	9464 KB	Output isn't correct
86	Incorrect	47 ms	9336 KB	Output isn't correct
87	Incorrect	40 ms	9308 KB	Output isn't correct
88	Incorrect	40 ms	9464 KB	Output isn't correct
89	Incorrect	38 ms	7584 KB	Output isn't correct
90	Incorrect	24 ms	7800 KB	Output isn't correct
91	Incorrect	39 ms	9208 KB	Output isn't correct
92	Incorrect	40 ms	9400 KB	Output isn't correct
93	Incorrect	42 ms	9208 KB	Output isn't correct
94	Incorrect	38 ms	9208 KB	Output isn't correct
95	Incorrect	40 ms	9208 KB	Output isn't correct
96	Incorrect	37 ms	8956 KB	Output isn't correct
97	Incorrect	39 ms	8824 KB	Output isn't correct
98	Incorrect	39 ms	8952 KB	Output isn't correct
99	Incorrect	44 ms	8700 KB	Output isn't correct
100	Incorrect	45 ms	8696 KB	Output isn't correct