Submission #58872

#	Time	Username	Problem	Language	Result	Execution time	Memory
58872		Benq	Bomb (IZhO17_bomb)	C++14	43 / 100	1097 ms	132096 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2505;

char gr[MX][MX];
int n,m;
pi len[MX][MX];

vi temp() {
    int mx = m;
    vi z; F0R(i,mx+1) z.pb(MOD);
    /*F0R(i,n) {
        F0R(j,m) cout << gr[i][j];
        cout << "\n";
    }
    cout << "----\n";*/
    F0Rd(j,m) {
        int lst = 0;
        F0R(i,n) {
            if (gr[i][j] == '1') {
                
            } else {
                FOR(I,lst,i) len[I][j] = {lst,i-1};
                lst = i+1;
            }
        }
        FOR(I,lst,n) len[I][j] = {lst,n-1};
        F0R(i,n) {
            if (gr[i][j] == '1' && (j == 0 || gr[i][j-1] == '0')) {
                pi cur = {-MOD,MOD};
                FOR(x,j,m+1) {
                    if (x == m || gr[i][x] == '0') {
                        mx = min(mx,x-j);
                        break;
                    }
                    cur.f = max(cur.f,len[i][x].f);
                    cur.s = min(cur.s,len[i][x].s);
                    z[x-j+1] = min(z[x-j+1],cur.s-cur.f+1);
                }
                // cout << i << " " << j << "\n";
            }
        }
    }
    FOR(i,mx+1,sz(z)) z[i] = 0;
    return z;
}

vi solve() {
    vi x = temp();
    F0R(i,n) for (int j = 0; j < m-1-j; j++) swap(gr[i][j],gr[i][m-1-j]);
    vi X = temp();
    F0R(i,sz(x)) x[i] = min(x[i],X[i]);
    return x;
}

int main() {
    // freopen("bomb.in","r",stdin);
    // freopen("bomb.out","w",stdout);
    cin >> n >> m;
    F0R(i,n) F0R(j,m) cin >> gr[i][j];
    vi x = solve();
    swap(n,m);
    F0R(i,MX) FOR(j,i+1,MX) swap(gr[i][j],gr[j][i]);
    vi y = solve();
    
    int ans = 0;
    F0R(i,sz(x)) F0R(j,sz(y)) if (j <= x[i] && i <= y[j]) ans = max(ans,i*j);
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 43 / 100