Submission #94314

#	Time	Username	Problem	Language	Result	Execution time	Memory
94314		Kastanda	Bomb (IZhO17_bomb)	C++11	90 / 100	105 ms	56824 KiB

bomb

#include<bits/stdc++.h>
using namespace std;
const int N = 2505;
int n, m, Mnx, R[N], up[N][N], dn[N][N];
char A[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", &A[i][1]);

    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];
        }
    memset(R, 63, sizeof(R));
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = n + 1, c = 0;
        for (int j = 1; j <= m; j++)
        {
            c ++;
            if (A[i][j] == '1')
            {
                l = max(l, up[i][j]);
                r = min(r, dn[i][j]);
                R[c] = min(R[c], r - l - 1);
            }
            else
            {
                if (A[i][j - 1] == '1')
                    R[c] = 0;
                l = 0; r = n + 1; c = 0;
            }
        }
        l = 0, r = n + 1, c = 0;
        for (int j = m; j; j--)
        {
            c ++;
            if (A[i][j] == '1')
            {
                l = max(l, up[i][j]);
                r = min(r, dn[i][j]);
                R[c] = min(R[c], r - l - 1);
            }
            else
            {
                if (A[i][j + 1] == '1')
                    R[c] = 0;
                l = 0; r = n + 1; c = 0;
            }
        }
    }
    int Mx_s = 0;
    for (int i = 1; i <= m; 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:8: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:10: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: 90 / 100