제출 #855546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855546		Alfraganus	Bomb (IZhO17_bomb)	C++17	21 / 100	1103 ms	67396 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define fs first
#define ss second
#define all(a) a.begin(), a.end()
#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x.fs << ' ' << x.ss << endl;

vector<vector<char>> a;
vector<vector<int>> sum;
int n, m;

bool check(int y)
{
    for (int j = 0; j < m; j++)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i][j] == '0')
                if (cnt > 0 and cnt < y)
                    return false;
                else
                    cnt = 0;
            else
                cnt++;
        }
        if (cnt > 0 and cnt < y)
            return false;
    }
    return true;
}

bool good(int y)
{
    for (int j = 0; j < n; j++)
    {
        int cnt = 0;
        for (int i = 0; i < m; i++)
        {
            if (a[j][i] == '0')
                if (cnt > 0 and cnt < y)
                    return false;
                else
                    cnt = 0;
            else
                cnt++;
        }
        if (cnt > 0 and cnt < y)
            return false;
    }
    return true;
}

int SUM(int i, int j, int x, int y)
{
    return sum[i][j] - (i - x < 0 ? 0 : sum[i - x][j]) - (j - y < 0 ? 0 : sum[i][j - y]) + (i - x < 0 or j - y < 0 ? 0 : sum[i - x][j - y]);
}

bool f1(int x, int y)
{
    vector<vector<char>> b = a;
    for(int i = n - 1; i >= x - 1; i --)
        for(int j = y - 1; j < m; j ++)
            if (SUM(i, j, x, y) == x * y)
                for (int k = 0; k < x; k++)
                    for (int t = 0; t < y; t++)
                        if (b[i - k][j - t] == '1')
                            b[i - k][j - t] = '2';
                        else
                            break;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cnt += (b[i][j] == '1');
    return cnt == 0;
}

void solve()
{
    cin >> n >> m;
    a.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    sum.resize(n, vector<int> (m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] == '1')
                sum[i][j] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            sum[i][j] += (i == 0 ? 0 : sum[i - 1][j]) + (j == 0 ? 0 : sum[i][j - 1]) - (i == 0 or j == 0 ? 0 : sum[i - 1][j - 1]);
    int lx = 1, rx = n;
    while (lx < rx)
    {
        int m = (lx + rx + 1) >> 1;
        if (check(m))
            lx = m;
        else
            rx = m - 1;
    }
    int ly = 1, ry = m;
    while (ly < ry)
    {
        int m = (ly + ry + 1) >> 1;
        if (good(m))
            ly = m;
        else
            ry = m - 1;
    }
    int LX = 1, RX = n;
    while (LX < RX)
    {
        int m = (LX + RX + 1) >> 1;
        if (f1(lx, m))
            LX = m;
        else
            RX = m - 1;
    }
    int LY = 1, RY = m;
    while (LY < RY)
    {
        int m = (LY + RY + 1) >> 1;
        if (f1(m, ly))
            LY = m;
        else
            RY = m - 1;
    }
    cout << max(lx * LX, ly * LY);
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("bomb.in", "r", stdin);
    // freopen("bomb.out", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp: In function 'bool f1(long long int, long long int)':
bomb.cpp:74:16: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   74 |             if (SUM(i, j, x, y) == x * y)
      |                ^

• Subtask 1: 21 / 100