Submission #39233

#	Time	Username	Problem	Language	Result	Execution time	Memory
39233		yerkimbekov	Bomb (IZhO17_bomb)	C++14	21 / 100	1000 ms	51200 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
 
int m,n,res=0,a[2505][2505],F[2505][2505];
 
int Suma(int u1,int v1,int u2,int v2)
{
    return a[u2][v2]-a[u1-1][v2]-a[u2][v1-1]+a[u1-1][v1-1];
}
 
int SumF(int u1,int v1,int u2,int v2)
{
    return F[u2][v2]-F[u1-1][v2]-F[u2][v1-1]+F[u1-1][v1-1];
}
 
bool Check(int mm,int nn)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            F[i][j]=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            F[i][j]=F[i-1][j]+F[i][j-1]-F[i-1][j-1];
            if(i+mm-1<=m&&j+nn-1&&Suma(i,j,i+mm-1,j+nn-1)==mm*nn)
                F[i][j]++;
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(Suma(i,j,i,j)==1&&SumF(max(i-mm+1,1),max(j-nn+1,1),i,j)==0)
                return false;
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>m>>n;
    char c;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>c;
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(c=='1');
        }
    int ll = 1, rr = m;
    while(ll <= rr){
      int i = (ll + rr) >> 1;
      bool tr = 0;
        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(Check(i,mid)==true)
            {
                tr = 1;
                res=max(res,i*mid);
                l=mid+1;
            }
            else
                r=mid-1;
        }
      if(tr){
        ll = i + 1;
      }else{
        rr = i - 1;
      }
    }
    cout << res;
}

• Subtask 1: 21 / 100