oj.uz

Submission #169911

# Submission time Handle Problem Language Result Execution time Memory
169911 2019-12-23T09:04:36 Z stefdasca Bomb (IZhO17_bomb) C++14
59 / 100
 797 ms 63992 KB 
#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 <= 250 && m <= 250)
    {
        int mxans = 0;
        for(int i = mny; i >= 1; --i)
            for(int j = mnx; j >= 1; --j)
            {
                if(i*j <= mxans)
                    continue;
                if(chk(i, j))
                    mxans = max(mxans, i*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
59.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 28 ms 26872 KB Output is correct
4 Correct 28 ms 26872 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 504 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 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 1144 KB Output is correct
18 Correct 3 ms 1144 KB Output is correct
19 Correct 7 ms 1464 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 1272 KB Output is correct
25 Correct 23 ms 1528 KB Output is correct
26 Correct 4 ms 1528 KB Output is correct
27 Correct 8 ms 4220 KB Output is correct
28 Incorrect 4 ms 4344 KB Output isn't correct
29 Incorrect 13 ms 5624 KB Output isn't correct
30 Incorrect 15 ms 6608 KB Output isn't correct
31 Incorrect 12 ms 5240 KB Output isn't correct
32 Incorrect 14 ms 6008 KB Output isn't correct
33 Incorrect 17 ms 6904 KB Output isn't correct
34 Incorrect 10 ms 4856 KB Output isn't correct
35 Incorrect 13 ms 6904 KB Output isn't correct
36 Correct 22 ms 6904 KB Output is correct
37 Correct 2 ms 632 KB Output is correct
38 Correct 18 ms 12920 KB Output is correct
39 Correct 2 ms 632 KB Output is correct
40 Correct 60 ms 16504 KB Output is correct
41 Correct 2 ms 632 KB Output is correct
42 Correct 21 ms 1528 KB Output is correct
43 Correct 792 ms 63764 KB Output is correct
44 Incorrect 18 ms 6904 KB Output isn't correct
45 Incorrect 456 ms 63692 KB Output isn't correct
46 Correct 448 ms 63864 KB Output is correct
47 Incorrect 461 ms 63864 KB Output isn't correct
48 Correct 490 ms 63864 KB Output is correct
49 Correct 336 ms 63780 KB Output is correct
50 Correct 485 ms 63864 KB Output is correct
51 Correct 490 ms 63760 KB Output is correct
52 Correct 514 ms 63736 KB Output is correct
53 Correct 451 ms 63864 KB Output is correct
54 Correct 443 ms 63732 KB Output is correct
55 Correct 436 ms 63864 KB Output is correct
56 Correct 573 ms 63764 KB Output is correct
57 Correct 507 ms 63736 KB Output is correct
58 Correct 531 ms 63756 KB Output is correct
59 Correct 482 ms 63852 KB Output is correct
60 Correct 470 ms 63832 KB Output is correct
61 Correct 489 ms 63768 KB Output is correct
62 Correct 723 ms 63808 KB Output is correct
63 Correct 797 ms 63864 KB Output is correct
64 Correct 647 ms 63692 KB Output is correct
65 Correct 439 ms 63860 KB Output is correct
66 Correct 440 ms 63860 KB Output is correct
67 Correct 462 ms 63764 KB Output is correct
68 Correct 536 ms 63780 KB Output is correct
69 Correct 514 ms 63720 KB Output is correct
70 Incorrect 252 ms 50224 KB Output isn't correct
71 Incorrect 426 ms 63684 KB Output isn't correct
72 Incorrect 486 ms 63792 KB Output isn't correct
73 Incorrect 432 ms 63788 KB Output isn't correct
74 Incorrect 447 ms 63736 KB Output isn't correct
75 Incorrect 447 ms 63864 KB Output isn't correct
76 Incorrect 461 ms 63992 KB Output isn't correct
77 Incorrect 491 ms 63780 KB Output isn't correct
78 Incorrect 546 ms 63736 KB Output isn't correct
79 Incorrect 351 ms 63736 KB Output isn't correct
80 Incorrect 320 ms 63740 KB Output isn't correct
81 Incorrect 376 ms 63788 KB Output isn't correct
82 Incorrect 497 ms 63792 KB Output isn't correct
83 Incorrect 570 ms 63780 KB Output isn't correct
84 Incorrect 320 ms 63736 KB Output isn't correct
85 Incorrect 458 ms 63832 KB Output isn't correct
86 Incorrect 362 ms 63736 KB Output isn't correct
87 Correct 427 ms 63764 KB Output is correct
88 Incorrect 461 ms 63756 KB Output isn't correct
89 Incorrect 419 ms 63764 KB Output isn't correct
90 Incorrect 303 ms 50112 KB Output isn't correct
91 Incorrect 478 ms 63768 KB Output isn't correct
92 Incorrect 443 ms 63736 KB Output isn't correct
93 Incorrect 380 ms 63764 KB Output isn't correct
94 Incorrect 418 ms 63864 KB Output isn't correct
95 Incorrect 493 ms 63752 KB Output isn't correct
96 Incorrect 471 ms 63864 KB Output isn't correct
97 Incorrect 362 ms 63828 KB Output isn't correct
98 Incorrect 502 ms 63752 KB Output isn't correct
99 Incorrect 417 ms 63776 KB Output isn't correct
100 Incorrect 384 ms 63780 KB Output isn't correct