Submission #169629

#	Time	Username	Problem	Language	Result	Execution time	Memory
169629		davitmarg	Bomb (IZhO17_bomb)	C++17	61 / 100	1099 ms	98552 KiB

bomb

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 2505;

int n, m, a[N][N], pr[N][N], lst[N][N], nxt[N][N];
char x;
int ans = 1;

void add(int sy, int sx, int y, int x)
{
    pr[sy][sx]++;
    pr[y][x]++;
    pr[sy][x]--;
    pr[y][sx]--;
}

int get(int sy, int sx, int y, int x)
{
    return a[y][x] - a[sy - 1][x] - a[y][sx - 1] + a[sy - 1][sx - 1];
}

bool check(int k, int q)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            pr[i][j] = 0;
    for (int i = 1; i + k - 1 <= n; i++)
        for (int j = 1; j + q - 1 <= m; j++)
            if (get(i, j, i + k - 1, j + q - 1) == k * q)
                add(i, j, i + k, j + q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            pr[i][j] += pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];
            if (get(i, j, i, j) != (bool)(pr[i][j]))
                return 0;
        }
    return 1;
}

void solve(int k)
{
    int l = max(ans / k, 1), r = m, mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (check(k, mid))
        {
            if (k * mid >= ans)
                ans = k * mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf(" %c", &x);
            a[i][j] += (x - '0');
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (get(i, j, i, j))
                lst[i][j] = 1 + lst[i - 1][j];

    int len = n;
    for (int i = n; i >= 1; i--)
        for (int j = m; j >= 1; j--)
            if (get(i, j, i, j))
            {
                nxt[i][j] = 1 + nxt[i + 1][j];
                len = min(len, nxt[i][j] + lst[i][j] - 1);
            }
    if (n <= 450)
        for (int i = 1; i <= len; i++)
            solve(i);
    else
    {
        for (int i = 1; i < len; i++)
            if (rand() % 150 == 0)
                solve(i);
        solve(len);
    }
    cout << ans << endl;
    return 0;
}

/*
 
6 6
000111
000111
001111
111100
111000
111000
 
*/

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &x);
             ~~~~~^~~~~~~~~~~

• Subtask 1: 61 / 100