제출 #1167992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167992		Mousa_Aboubaker	축구 경기장 (IOI23_soccer)	C++20	6 / 100	211 ms	63204 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector

// what is the idea of my solution ?

/*

- get for each pair(i, j) j >= i how much I can extend it to both, top, and bottom
- then I will make sure that when I will query for something max(i, j) it will return the max in any of its subarrays
- my current solution idea should be O(n ^ 3 * (log(n ^ 3))), or something like this

*/

void chmax(int &a, int b)
{
    if (a < b)
        a = b;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int n = N;
    auto f = F;
    vec<vec<int>> pref(n + 1, vec<int>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + f[i - 1][j - 1];
    auto query = [&](int i1, int j1, int i2, int j2) -> int
    {
        i1++, j1++, i2++, j2++;
        return pref[i2][j2] - pref[i1 - 1][j2] - pref[i2][j1 - 1] + pref[i1 - 1][j1 - 1];
    };
    if (query(0, 0, n - 1, n - 1) <= 1)
    {
        if (query(0, 0, n - 1, n - 1) == 0)
        {
            return n * n;
        }

        pair<int, int> idx;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (f[i][j] == 1)
                {
                    idx = {i + 1, j + 1};
                }
            }
        }

        int res1 = n * n - idx.first * idx.second;
        int res2 = n * n - (n - idx.first + 1) * (n - idx.second + 1);
        int res3 = n * n - (n - idx.first + 1) * idx.second;
        int res4 = n * n - idx.first * (n - idx.second + 1);

        return max({res1, res2, res3, res4});
    }
    if (n > 30)
    {
        return n * n - query(0, 0, n - 1, n - 1);
    }
    vec top(n, vec(n, vec<int>(n, 0))), down(top), right(top), left(top);
    for (int i = 0; i < n; i++)
    {
        priority_queue<tuple<int, int, int>> pq;
        for (int j = 0; j < n; j++)
        {
            if (f[i][j])
                continue;
            for (int k = j; k < n; k++)
            {
                if (f[i][k])
                    break;
                int l = 0, r = i, ans = i;
                while (l <= r)
                {
                    int md = (l + r) / 2;
                    if (query(md, j, i, k) == 0)
                    {
                        r = md - 1;
                        ans = md;
                    }
                    else
                    {
                        l = md + 1;
                    }
                }
                pq.push({(i - ans + 1) * (k - j + 1), j, k});
            }
        }
        while (not pq.empty())
        {
            auto [v, j, k] = pq.top();
            pq.pop();

            for (int x = j; x >= 0; x--)
                for (int y = k; y < n; y++)
                    chmax(top[i][x][y], v);
        }

        for (int j = 0; j < n; j++)
        {
            if (f[i][j])
                continue;
            for (int k = j; k < n; k++)
            {
                if (f[i][k])
                    break;
                int l = i, r = n - 1, ans = i;
                while (l <= r)
                {
                    int md = (l + r) / 2;
                    if (query(i, j, md, k) == 0)
                    {
                        l = md + 1;
                        ans = md;
                    }
                    else
                    {
                        r = md - 1;
                    }
                }
                pq.push({(ans - i + 1) * (k - j + 1), j, k});
            }
        }
        while (not pq.empty())
        {
            auto [v, j, k] = pq.top();
            pq.pop();

            for (int x = j; x >= 0; x--)
                for (int y = k; y < n; y++)
                    chmax(down[i][x][y], v);
        }

        for (int j = 0; j < n; j++)
        {
            if (f[j][i])
                continue;
            for (int k = j; k < n; k++)
            {
                if (f[k][i])
                    break;
                int l = i, r = n - 1, ans = i;
                while (l <= r)
                {
                    int md = (l + r) / 2;
                    if (query(j, i, k, md) == 0)
                    {
                        l = md + 1;
                        ans = md;
                    }
                    else
                    {
                        r = md - 1;
                    }
                }
                pq.push({(ans - i + 1) * (k - j + 1), j, k});
            }
        }
        while (not pq.empty())
        {
            auto [v, j, k] = pq.top();
            pq.pop();

            for (int x = j; x >= 0; x--)
                for (int y = k; y < n; y++)
                    chmax(right[i][x][y], v);
        }

        for (int j = 0; j < n; j++)
        {
            if (f[j][i])
                continue;
            for (int k = j; k < n; k++)
            {
                if (f[k][i])
                    break;
                int l = 0, r = i, ans = i;
                while (l <= r)
                {
                    int md = (l + r) / 2;
                    if (query(j, md, k, i) == 0)
                    {
                        l = md + 1;
                        ans = md;
                    }
                    else
                    {
                        r = md - 1;
                    }
                }
                pq.push({(i - ans + 1) * (k - j + 1), j, k});
            }
        }
        while (not pq.empty())
        {
            auto [v, j, k] = pq.top();
            pq.pop();

            for (int x = j; x >= 0; x--)
                for (int y = k; y < n; y++)
                    chmax(left[i][x][y], v);
        }
    }
    int mx = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (f[i][j])
                continue;
            for (int k = j; k < n; k++)
            {
                if (f[i][k])
                    break;
                int l = i, r = n - 1, ans = i;
                while (l <= r)
                {
                    int md = (l + r) / 2;
                    if (query(i, j, md, k) == 0)
                    {
                        l = md + 1;
                        ans = md;
                    }
                    else
                        r = md - 1;
                }
                int v = (k - j + 1) * (ans - i + 1);
                if (i != 0)
                {
                    v += top[i - 1][j][k];
                    // cout << top[i - 1][j][k] << ' ';
                }
                if (ans != n - 1)
                {
                    v += down[ans + 1][j][k];
                    // cout << down[ans + 1][j][k] << ' ';
                }
                if (j != 0)
                {
                    v += left[j - 1][i][ans];
                    // cout << left[j - 1][i][ans] << ' ';
                }
                if (k != n - 1)
                {
                    v += right[k + 1][i][ans];
                    // cout << right[k + 1][i][ans] << ' ';
                }
                chmax(mx, v);
                // cout << i << ' ' << ans << ' ' << j << ' ' << k << ' ' << v << '\n';
            }
        }
    }
    return mx;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30