Submission #833188

#	Time	Username	Problem	Language	Result	Execution time	Memory
833188		vjudge1	Bomb (IZhO17_bomb)	C++17	29 / 100	1094 ms	61756 KiB

bomb

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

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
typedef long long ll;
const ll MAXN = 25e2 + 5;
const ll INF = 1e9;
#define endl '\n'
#define pll pair <ll, ll>
#define fi first
#define se second

ll n, m;
string a [MAXN];
ll pf [MAXN][MAXN];
bool uda [MAXN][MAXN];

int main(){
    cin >> n >> m;
    for(ll i = 1; i <= n; i++){
        string dum; cin >> dum;
        a[i] = '2' + dum;
    }
    if(n == 1 && m == 1){
        cout << a[1][1] << endl;
        exit(0);
    }
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            pf[i][j] = pf[i][j-1];
            if(a[i][j] == '1') pf[i][j]++;
        }
    }
    for(ll j = 1; j <= m; j++){
        for(ll i = 1; i <= n; i++){
            pf[i][j] += pf[i-1][j];
        }
    }
    // cout << endl;
    // for(ll i = 1; i <= n; i++){
    //     for(ll j = 1; j <= m; j++){
    //         cout << pf[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    ll mx = 0;
    for(ll x = 1; x <= n; x++){
        for(ll y = 1; y <= m; y++){
            for(ll i = 1; i <= n; i++){
                for(ll j = 1; j <= m; j++) uda[i][j] = false;
            }
            for(ll i = 1; i+x-1 <= n; i++){
                for(ll j = 1; j+y-1 <= m; j++){
                    ll sum = pf[i+x-1][j+y-1] - pf[i-1][j+y-1] - pf[i+x-1][j-1] + pf[i-1][j-1];
                    if(sum == x*y){
                        for(ll lx = i; lx <= i+x-1; lx++){
                            for(ll ly = j; ly <= j+y-1; ly++){
                                uda[lx][ly] = true;
                            }
                        }
                    }
                }
            }
            bool bnr = true;
            for(ll i = 1; i <= n; i++){
                for(ll j = 1; j <= m; j++){
                    if(!uda[i][j] && a[i][j] == '1'){
                        bnr = false;
                        break;
                    }
                }
            }
            if(bnr){
                mx = max(mx, x*y);
            }
        }
    }
    cout << mx << endl;
}

• Subtask 1: 29 / 100