Submission #855504

#	Time	Username	Problem	Language	Result	Execution time	Memory
855504		Alfraganus	Bomb (IZhO17_bomb)	C++17	9 / 100	1106 ms	67824 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;
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(vector<vector<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;
    vector<vector<int>> sum(n, vector<int> (m));
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            if(b[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]);
        }
    }
    for(int i = x - 1; i < n; i ++){
        for(int j = y - 1; j < m; j ++){
            if(SUM(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];
    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 = n;
    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;
    }
}

• Subtask 1: 9 / 100