Submission #682565

#	Time	Username	Problem	Language	Result	Execution time	Memory
682565		opPO	Bomb (IZhO17_bomb)	C++17	41 / 100	1107 ms	79792 KiB

bomb

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 2501;
int n, m, a[N][N], pref[N][N], p[N][N];

int get(int x1, int y1, int x2, int y2)
{
    return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}

bool check(int h, int w)
{
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) p[i][j] = 0;
    for (int x1 = 1; x1 <= n; x1++)
    {
        for (int y1 = 1; y1 <= m; y1++)
        {
            int x2 = x1 + h - 1, y2 = y1 + w - 1;
            if (x2 > n || y2 > m) break;
            if (get(x1, y1, x2, y2) == h * w)
            {
                p[x1][y1]++;
                p[x1][y2 + 1]--;
                p[x2 + 1][y1]--;
                p[x2 + 1][y2 + 1]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            p[i][j] += p[i - 1][j];
            p[i][j] += p[i][j - 1];
            p[i][j] -= p[i - 1][j - 1];
            if (a[i][j] == 1 && p[i][j] == 0) return false;
        }
    }
    return true;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            a[i][j] = c - '0';
            pref[i][j] += a[i][j];
            pref[i][j] += pref[i - 1][j];
            pref[i][j] += pref[i][j - 1];
            pref[i][j] -= pref[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int h = 1; h <= n; h++)
    {
        int l = 0, r = m;
        while (l < r)
        {
            int mid = (l + r + 1) / 2;
            if (check(h, mid)) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, h * l);
    }
    cout << ans;
}

int32_t main()
{
//    freopen("bomb.in", "r", stdin);
//    freopen("bomb.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 41 / 100