Submission #944676

#	Time	Username	Problem	Language	Result	Execution time	Memory
944676		GrandTiger1729	Bomb (IZhO17_bomb)	C++17	0 / 100	285 ms	37288 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; i++)
    {
        cin >> g[i];
    }
    int xx = INF, yy = INF;
    {
        vector<vector<int>> rr(n, vector<int>(m));
        for (int i = 0; i < n; i++)
        {
            int cur = m;
            for (int j = m - 1; j >= 0; j--)
            {
                if (g[i][j] == '0')
                {
                    cur = j;
                }
                rr[i][j] = cur;
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (rr[i][j] - j > 0)
                {
                    xx = min(xx, rr[i][j] - j);
                }
            }
        }
        for (int j = 0; j < m; j++)
        {
            int cur = n;
            for (int i = n - 1; i >= 0; i--)
            {
                if (g[i][j] == '0')
                {
                    cur = i;
                }
                rr[i][j] = cur;
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (rr[i][j] - i > 0)
                {
                    yy = min(yy, rr[i][j] - i);
                }
            }
        }
    }
    vector<int> res(yy, xx);
    auto solve = [&]()
    {
        vector<vector<int>> rr(n, vector<int>(m));
        for (int i = 0; i < n; i++)
        {
            int cur = m;
            for (int j = m - 1; j >= 0; j--)
            {
                if (g[i][j] == '0')
                {
                    cur = j;
                }
                rr[i][j] = cur;
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (rr[i][j] - j > 0)
                {
                    res[0] = min(res[0], rr[i][j] - j);
                }
            }
        }
        for (int i = 1; i < res.size(); i++)
        {
            res[i] = min(res[i], res[i - 1]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (g[i][j] == '1' && (i == 0 || g[i - 1][j] == '0') && (j == 0 || g[i][j - 1] == '0'))
                {
                    int k = i, cur = INF;
                    while (k < n && k - i < res.size() && g[k][j] == '1')
                    {
                        cur = min(cur, rr[k][j] - j);
                        res[k - i] = min(res[k - i], cur);
                        k++;
                    }
                    res.resize(k - i);
                }
            }
        }
    };
    for (int tt = 0; tt < 2; tt++)
    {
        solve();
        reverse(g.begin(), g.end());
        solve();
        for (int i = 0; i < n; i++)
        {
            reverse(g[i].begin(), g[i].end());
        }
    }
    int ans = 0;
    for (int i = 0; i < res.size(); i++)
    {
        ans = max(ans, (i + 1) * res[i]);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

bomb.cpp: In lambda function:
bomb.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 1; i < res.size(); i++)
      |                         ~~^~~~~~~~~~~~
bomb.cpp:100:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                     while (k < n && k - i < res.size() && g[k][j] == '1')
      |                                     ~~~~~~^~~~~~~~~~~~
bomb.cpp: In function 'int main()':
bomb.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < res.size(); i++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 100