Submission #94315

#	Time	Username	Problem	Language	Result	Execution time	Memory
94315		Kastanda	Bomb (IZhO17_bomb)	C++11	100 / 100	127 ms	56952 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
const int N = 2505;
int n, m, Mnx, Mny, R[N], up[N][N], dn[N][N];
char A[N][N];
inline void Init()
{
    Mnx = m; Mny = n;

    for (int i = 1; i <= n; i++)
    {
        int last = 0;
        for (int j = 1; j <= m; j++)
            if (A[i][j] == '0')
            {
                if (last != j - 1)
                    Mnx = min(Mnx, j - last - 1);
                last = j;
            }
        if (last != m)
            Mnx = min(Mnx, m - last);
    }

    for (int i = 1; i <= m; i++)
    {
        int last = 0;
        for (int j = 1; j <= n; j++)
            if (A[j][i] == '0')
            {
                if (last != j - 1)
                    Mny = min(Mny, j - last - 1);
                last = j;
            }
        if (last != n)
            Mny = min(Mny, n - last);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", &A[i][1]);
    Init();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            up[i][j] = i - 1;
            if (A[i - 1][j] == '1')
                up[i][j] = up[i - 1][j];
        }
    for (int i = n; i; i--)
        for (int j = 1; j <= m; j++)
        {
            dn[i][j] = i + 1;
            if (A[i + 1][j] == '1')
                dn[i][j] = dn[i + 1][j];
        }
    for (int i = 0; i <= Mnx; i++)
        R[i] = Mny;
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = n + 1, c = 0;
        for (int j = 1; j <= m; j++)
        {
            if (A[i][j] == '1')
            {
                c ++;
                l = max(l, up[i][j]);
                r = min(r, dn[i][j]);
                R[c] = min(R[c], r - l - 1);
            }
            else
                l = 0, r = n + 1, c = 0;
        }
        l = 0, r = n + 1, c = 0;
        for (int j = m; j; j--)
        {
            if (A[i][j] == '1')
            {
                c ++;
                l = max(l, up[i][j]);
                r = min(r, dn[i][j]);
                R[c] = min(R[c], r - l - 1);
            }
            else
                l = 0, r = n + 1, c = 0;
        }
    }
    int Mx_s = 0;
    for (int i = 1; i <= Mnx; i++)
    {
        R[i] = min(R[i], R[i - 1]);
        Mx_s = max(Mx_s, i * R[i]);
    }
    return !printf("%d", Mx_s);
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &A[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100