Submission #334693

#	Time	Username	Problem	Language	Result	Execution time	Memory
334693		limabeans	Bomb (IZhO17_bomb)	C++17	100 / 100	445 ms	76012 KiB

bomb

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl








const int maxn = 2555;
const int inf = 1e9;


int n,m;
int a[maxn][maxn];

int up[maxn][maxn], dw[maxn][maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    for (int i=0; i<n; i++) {
	string s;
	cin>>s;
	for (int j=0; j<m; j++) {
	    a[i][j]=int(s[j]-'0');
	}
    }


    for (int j=0; j<m; j++) {
	for (int i=0; i<n; i++) {
	    if (a[i][j]==1) {
		up[i][j]=1;
		if (i>0) up[i][j]+=up[i-1][j];
	    }
	}
	for (int i=n-1; i>=0; i--) {
	    if (a[i][j]==1) {
		dw[i][j]=1;
		dw[i][j]+=dw[i+1][j];
	    }
	}
    }


    int minW = inf;
    int minH = inf;
    for (int j=0; j<m; j++) {
	int cur = 0;
	for (int i=0; i<n; i++) {
	    if (a[i][j]==1) {
		cur++;
	    } else {
		if (cur>0) minH=min(minH,cur);
		cur=0;
	    }
	}
	if (cur>0) minH=min(minH,cur);
    }


    for (int i=0; i<n; i++) {
	int cur = 0;
	for (int j=0; j<m; j++) {
	    if (a[i][j]) {
		cur++;
	    } else {
		if (cur>0) minW=min(minW,cur);
		cur=0;
	    }
	}
	if (cur>0) minW=min(minW,cur);
    }


    // watch(minW);
    // watch(minH);

    vector<int> dp(maxn+10, minH); //dp[w]: given width w, what's feasible height h for rectangle hxw

    // left to right
    for (int i=0; i<n; i++) {
	int u=inf;
	int d=inf;
	int col=0;
	for (int j=0; j<m; j++) {
	    if (a[i][j]==1) {
		u=min(u,up[i][j]);
		d=min(d,dw[i][j]);
		++col;
		dp[col]=min(dp[col],u+d-1);
	    } else {
		u=d=inf;
		col=0;
	    }
	}
    }

    // right to left
    for (int i=0; i<n; i++) {
	int u=inf;
	int d=inf;
	int col=0;
	for (int j=m-1; j>=0; j--) {
	    if (a[i][j]==1) {
		u=min(u,up[i][j]);
		d=min(d,dw[i][j]);
		++col;
		dp[col]=min(dp[col],u+d-1);
	    } else {
		u=d=inf;
		col=0;
	    }
	}
    }

    int res = dp[1];
    for (int i=2; i<=minW; i++) {
	dp[i]=min(dp[i],dp[i-1]);
	res=max(res,i*dp[i]);
    }

    cout<<res<<endl;    
    return 0;
}

• Subtask 1: 100 / 100