Submission #944678

#	Time	Username	Problem	Language	Result	Execution time	Memory
944678		GrandTiger1729	Bomb (IZhO17_bomb)	C++17	99 / 100	125 ms	32176 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;
    {
        for (int i = 0; i < n; i++)
        {
            int l = 0, r = 0;
            while (l < m)
            {
                while (l < m && g[i][l] == '0')
                {
                    l++;
                }
                if (l == m)
                {
                    break;
                }
                r = l;
                while (r < m && g[i][r] == '1')
                {
                    r++;
                }
                xx = min(xx, r - l);
                l = r;
            }
        }
        for (int j = 0; j < m; j++)
        {
            int l = 0, r = 0;
            while (l < n)
            {
                while (l < n && g[l][j] == '0')
                {
                    l++;
                }
                if (l == n)
                {
                    break;
                }
                r = l;
                while (r < n && g[r][j] == '1')
                {
                    r++;
                }
                yy = min(yy, r - l);
                l = r;
            }
        }
    }
    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 (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:85:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                     while (k < n && k - i < res.size() && g[k][j] == '1')
      |                                     ~~~~~~^~~~~~~~~~~~
bomb.cpp: In function 'int main()':
bomb.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < res.size(); i++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 99 / 100