제출 #94309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94309		Kastanda	Bomb (IZhO17_bomb)	C++11	35 / 100	1095 ms	58744 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];
int qu[N], F[N];
char A[N][N];
inline int Calc(int lenx)
{
    if (lenx > Mnx)
        return 0;

    int Mn = n;
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = 0;
        for (int j = 1; j <= m; j++)
        {
            while (r - l && dn[i][j] <= dn[i][qu[r-1]])
                r --;
            qu[r ++] = j;
            if (qu[l] <= j - lenx)
                l ++;
            F[j - lenx + 1] = dn[i][qu[l]] - 1;
        }
        l = r = 0;
        for (int j = 1; j <= m; j++)
        {
            while (r - l && up[i][j] >= up[i][qu[r-1]])
                r --;
            qu[r ++] = j;
            if (qu[l] <= j - lenx)
                l ++;
            F[j - lenx + 1] -= up[i][qu[l]];
        }
        l = r = 0;
        for (int j = 1; j <= m; j++)
        {
            if (j + lenx - 1 <= m)
            {
                F[j] = max(F[j], 0);
                while (r - l && F[j] >= F[qu[r-1]])
                    r --;
                qu[r ++] = j;
            }
            while (qu[l] <= j - lenx)
                l ++;
            if (A[i][j] == '1')
                Mn = min(Mn, F[qu[l]]);
        }
    }
    return (Mn);
}
inline void Init()
{
    Mnx = m;
    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);
    }
}
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];

            if (A[i][j] == '0')
                dn[i][j] = 0, up[i][j] = n + 1;
        }

    memset(R, -1, sizeof(R));
    R[1] = Calc(1) * 1;
    R[Mnx] = Calc(Mnx) * Mnx;

    int le = 1, ri = Mnx + 1, md;
    while (ri - le > 1)
    {
        md = (le + ri) >> 1;
        if (R[md] == -1) R[md] = Calc(md) * md;
        if (R[md-1] == -1) R[md-1] = Calc(md-1) * (md-1);

        if (R[md] > R[md-1])
            le = md;
        else
            ri = md;
    }
    return !printf("%d", R[le]);
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp: In function 'int main()':
bomb.cpp:72: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:74: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: 35 / 100