Submission #35815

#	Time	Username	Problem	Language	Result	Execution time	Memory
35815		dqhungdl	Bomb (IZhO17_bomb)	C++14	30 / 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');
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(Check(i,j)==true)
                res=max(res,i*j);
    cout<<res;
}

• Subtask 1: 30 / 100