Submission #1164059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164059		Mousa_Aboubaker	Soccer Stadium (IOI23_soccer)	C++20	6 / 100	214 ms	63288 KiB

soccer

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

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
    {
        return pref[i2][j2] - pref[i1 - 1][j2] - pref[i2][j1 - 1] + pref[i1 - 1][j1 - 1];
    };
    if (query(1, 1, n, n) <= 1)
    {
        if (query(1, 1, n, n) == 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(1, 1, n, n);
    }
    int mx = 0;
    for (int x1 = 1; x1 <= n; x1++)
    {
        for (int y1 = 1; y1 <= n; y1++)
        {
            int x2 = x1, y3 = y1;
            for (int y2 = y1; y2 <= n; y2++)
            {
                for (int x3 = x1; x3 <= n; x3++)
                {
                    int x4 = x3;
                    int y4 = y2;
                    if (query(x1, y1, x4, y4) > 0)
                    {
                        x3 = n;
                        y2 = n;
                        break;
                    }
                    // extend up
                    // extend down
                    // extend right
                    // extend left
                    // the final result is, inner square + the new four squares
                    int res = (x4 - x1 + 1) * (y4 - y1 + 1);
                    // extend up
                    int l = 1, r = x1, ans = x1;
                    while (l <= r)
                    {
                        int md = (l + r) / 2;
                        if (query(x1, md, x2, y2) == 0)
                        {
                            r = md - 1;
                            ans = md;
                        }
                        else
                        {
                            l = md + 1;
                        }
                    }
                    res += (x1 - ans) * (y2 - y1 + 1);
                    // extend down
                    l = x4, r = n, ans = x4;
                    while (l <= r)
                    {
                        int md = (l + r) / 2;
                        if (query(x3, y3, md, y4) == 0)
                        {
                            l = md + 1;
                            ans = md;
                        }
                        else
                        {
                            r = md - 1;
                        }
                    }
                    res += (ans - x4) * 1ll * (y2 - y1 + 1);
                    // extend left
                    l = 1, r = y1, ans = y1;
                    while (l <= r)
                    {
                        int md = (l + r) / 2;
                        if (query(x1, md, x3, y3) == 0)
                        {
                            r = md - 1;
                            ans = md;
                        }
                        else
                        {
                            l = md + 1;
                        }
                    }
                    res += (y1 - ans) * 1ll * (x3 - x1 + 1);
                    // extend right
                    l = y4, r = n, ans = y4;
                    while (l <= r)
                    {
                        int md = (l + r) / 2;
                        if (query(x2, y2, x4, md) == 0)
                        {
                            l = md + 1;
                            ans = md;
                        }
                        else
                        {
                            r = md - 1;
                        }
                    }
                    res += (ans - y4) * 1ll * (x4 - x1 + 1);
                    if (res > mx)
                        mx = res;
                }
            }
        }
    }
    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