Submission #366825

#	Time	Username	Problem	Language	Result	Execution time	Memory
366825		nicolaalexandra	Bomb (IZhO17_bomb)	C++14	100 / 100	680 ms	125420 KiB

bomb

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

int n,m,i,j;
char s[DIM];
int dp_up[DIM][DIM],dp_down[DIM][DIM],dp_left[DIM][DIM],dp_right[DIM][DIM];
int a[DIM][DIM],dp[DIM];

int main (){

    //ifstream cin ("bomb.in");
    //ofstream cout ("bomb.out");

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

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            if (a[i][j]){
                dp_up[i][j] = 1 + dp_up[i-1][j];
                dp_left[i][j] = 1 + dp_left[i][j-1];
            }}

    for (i=n;i;i--)
        for (j=m;j;j--){
            if (a[i][j]){
                dp_down[i][j] = 1 + dp_down[i+1][j];
                dp_right[i][j] = 1 + dp_right[i][j+1];
            }}

    /// pot sa am maxim dimensiunile h,w
    /// dp[i] - latimea maxima a unui dreptunghi cu inaltimea i

    for (i=1;i<=n;i++)
        dp[i] = m+1;

    int w = m, h = n;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            if (!a[i][j])
                continue;
            w = min (w,dp_right[i][j] + dp_left[i][j] - 1);
            h = min (h,dp_up[i][j] + dp_down[i][j] - 1);

            dp[1] = min (dp[1],dp_left[i][j] + dp_right[i][j] - 1);
        }

    for (j=1;j<=m;j++){
        int st = 0, dr = m+1, cnt = 0;
        for (i=1;i<=n;i++){
            if (a[i][j]){
                st = max (st,j - dp_left[i][j] + 1);
                dr = min (dr,j + dp_right[i][j] - 1);
                cnt++;
                dp[cnt] = min (dp[cnt],dr-st+1);
            } else {
                cnt = 0;
                st = 0, dr = m+1;
            }}}

    /// trb sa fac acelasi lucru si invers

    for (j=1;j<=m;j++){
        int st = 0, dr = m+1, cnt = 0;
        for (i=n;i;i--){
            if (a[i][j]){
                st = max (st,j - dp_left[i][j] + 1);
                dr = min (dr,j + dp_right[i][j] - 1);
                cnt++;
                dp[cnt] = min (dp[cnt],dr-st+1);
            } else {
                cnt = 0;
                st = 0, dr = m+1;
            }}}

    int sol = 0;
    for (i=1;i<=h;i++){
        if (i > 1)
            dp[i] = min (dp[i],dp[i-1]);
        sol = max (sol,dp[i] * i);
    }

    cout<<sol;


    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         cin>>s+1;
      |              ~^~

• Subtask 1: 100 / 100