oj.uz

Submission #169915

# Submission time Handle Problem Language Result Execution time Memory
169915 2019-12-23T09:11:47 Z stefdasca Bomb (IZhO17_bomb) C++14
67 / 100
 1000 ms 60792 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 <= 450 && m <= 450)
    {
        int mxans = 0;
        for(int i = n; i >= 1; --i)
        {
            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
67.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 31 ms 26744 KB Output is correct
4 Correct 27 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 3 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 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 632 KB Output is correct
17 Correct 4 ms 1020 KB Output is correct
18 Correct 4 ms 1148 KB Output is correct
19 Correct 7 ms 1400 KB Output is correct
20 Correct 7 ms 1400 KB Output is correct
21 Correct 4 ms 1016 KB Output is correct
22 Correct 6 ms 1272 KB Output is correct
23 Correct 8 ms 1528 KB Output is correct
24 Correct 6 ms 1400 KB Output is correct
25 Correct 10 ms 1528 KB Output is correct
26 Correct 11 ms 1528 KB Output is correct
27 Correct 255 ms 4316 KB Output is correct
28 Correct 241 ms 4444 KB Output is correct
29 Correct 512 ms 5624 KB Output is correct
30 Correct 731 ms 6612 KB Output is correct
31 Correct 417 ms 5372 KB Output is correct
32 Correct 555 ms 6008 KB Output is correct
33 Correct 875 ms 7032 KB Output is correct
34 Correct 200 ms 4856 KB Output is correct
35 Correct 663 ms 7032 KB Output is correct
36 Execution timed out 1033 ms 6948 KB Time limit exceeded
37 Correct 2 ms 632 KB Output is correct
38 Correct 17 ms 9820 KB Output is correct
39 Correct 2 ms 632 KB Output is correct
40 Correct 60 ms 16376 KB Output is correct
41 Correct 3 ms 632 KB Output is correct
42 Correct 9 ms 1528 KB Output is correct
43 Correct 773 ms 60728 KB Output is correct
44 Correct 789 ms 7032 KB Output is correct
45 Incorrect 447 ms 60728 KB Output isn't correct
46 Correct 436 ms 60788 KB Output is correct
47 Incorrect 458 ms 60708 KB Output isn't correct
48 Correct 442 ms 60656 KB Output is correct
49 Correct 335 ms 60660 KB Output is correct
50 Correct 473 ms 60712 KB Output is correct
51 Correct 475 ms 60680 KB Output is correct
52 Correct 446 ms 60664 KB Output is correct
53 Correct 425 ms 60792 KB Output is correct
54 Correct 440 ms 60664 KB Output is correct
55 Correct 419 ms 60748 KB Output is correct
56 Correct 568 ms 59384 KB Output is correct
57 Correct 518 ms 60280 KB Output is correct
58 Correct 550 ms 59584 KB Output is correct
59 Correct 476 ms 58104 KB Output is correct
60 Correct 466 ms 58104 KB Output is correct
61 Correct 493 ms 58076 KB Output is correct
62 Correct 728 ms 57868 KB Output is correct
63 Correct 742 ms 57832 KB Output is correct
64 Correct 621 ms 57720 KB Output is correct
65 Correct 405 ms 57820 KB Output is correct
66 Correct 434 ms 57884 KB Output is correct
67 Correct 462 ms 57720 KB Output is correct
68 Correct 498 ms 57828 KB Output is correct
69 Correct 491 ms 57776 KB Output is correct
70 Incorrect 247 ms 46328 KB Output isn't correct
71 Incorrect 430 ms 57888 KB Output isn't correct
72 Incorrect 444 ms 57768 KB Output isn't correct
73 Incorrect 416 ms 57848 KB Output isn't correct
74 Incorrect 443 ms 57852 KB Output isn't correct
75 Incorrect 448 ms 57720 KB Output isn't correct
76 Incorrect 449 ms 57720 KB Output isn't correct
77 Incorrect 481 ms 57848 KB Output isn't correct
78 Incorrect 508 ms 57848 KB Output isn't correct
79 Incorrect 314 ms 57848 KB Output isn't correct
80 Incorrect 306 ms 57848 KB Output isn't correct
81 Incorrect 356 ms 57848 KB Output isn't correct
82 Incorrect 490 ms 57848 KB Output isn't correct
83 Incorrect 497 ms 57804 KB Output isn't correct
84 Incorrect 284 ms 57848 KB Output isn't correct
85 Incorrect 436 ms 57720 KB Output isn't correct
86 Incorrect 369 ms 57848 KB Output isn't correct
87 Correct 413 ms 57848 KB Output is correct
88 Incorrect 448 ms 57820 KB Output isn't correct
89 Incorrect 407 ms 57824 KB Output isn't correct
90 Incorrect 293 ms 46328 KB Output isn't correct
91 Incorrect 447 ms 57820 KB Output isn't correct
92 Incorrect 435 ms 57720 KB Output isn't correct
93 Incorrect 373 ms 57848 KB Output isn't correct
94 Incorrect 417 ms 57816 KB Output isn't correct
95 Incorrect 541 ms 57720 KB Output isn't correct
96 Incorrect 491 ms 57776 KB Output isn't correct
97 Incorrect 400 ms 57712 KB Output isn't correct
98 Incorrect 541 ms 57720 KB Output isn't correct
99 Incorrect 441 ms 57760 KB Output isn't correct
100 Incorrect 372 ms 57788 KB Output isn't correct