Submission #1011315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011315		boris_mihov	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2367 ms	154708 KiB

soccer

#include "soccer.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 2000 + 10;
const int INF  = 1e9;

int n;
int p[MAXN][MAXN];
int t[MAXN][MAXN];

inline int sum(int rowB, int colB, int rowE, int colE)
{
    return p[rowE][colE] - p[rowB - 1][colE] - p[rowE][colB - 1] + p[rowB - 1][colB - 1];
}

std::pair <int,int> extend(int row, int colB, int colE)
{
    assert(row > 0);
    std::pair <int,int> sol;
    int l = 0, r = row, mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (sum(mid, colB, row, colE) != 0) l = mid;
        else r = mid;
    }

    sol.first = r;
    l = row, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (sum(row, colB, mid, colE) == 0) l = mid;
        else r = mid;
    }

    sol.second = l;
    return sol;
}

std::vector <std::pair <int,int>> split(int row, int colB, int colE)
{
    int last = colB;
    std::vector <std::pair <int,int>> sol;
    for (int i = colB ; i <= colE ; ++i)
    {
        if (t[row][i])
        {
            if (last < i)
            {
                sol.push_back({last, i - 1});
            }

            last = i + 1;
        }
    }

    if (last <= colE) sol.push_back({last, colE});
    return sol;
}

std::map <std::array <int,4>, int> dp;
int f(int rowB, int colB, int rowE, int colE)
{
    if (colB > colE)
    {
        return 0;
    }

    if (rowB == 1 && rowE == n)
    {
        return 0;
    }
    
    if (dp.count({rowB, colB, rowE, colE}))
    {
        return dp[{rowB, colB, rowE, colE}];
    }

    int res = 0;
    if (rowB > 1)
    {
        std::vector <std::pair <int,int>> v = split(rowB - 1, colB, colE);
        for (const auto &[nextColB, nextColE] : v)
        {
            int lastRes = res;
            auto [nextRowB, nextRowE] = extend(rowB - 1, nextColB, nextColE);
            res = std::max(res, (nextColE - nextColB + 1) * (nextRowE - nextRowB + 1 - (rowE - rowB + 1)) + f(nextRowB, nextColB, nextRowE, nextColE));
        }
    }

    if (rowE < n)
    {
        std::vector <std::pair <int,int>> v = split(rowE + 1, colB, colE);
        for (const auto &[nextColB, nextColE] : v)
        {
            int lastRes = res;
            auto [nextRowB, nextRowE] = extend(rowE + 1, nextColB, nextColE);
            res = std::max(res, (nextColE - nextColB + 1) * (nextRowE - nextRowB + 1 - (rowE - rowB + 1)) + f(nextRowB, nextColB, nextRowE, nextColE));
        }
    }

    return dp[{rowB, colB, rowE, colE}] = res;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n = N;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            t[i][j] = F[i - 1][j - 1];
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + t[i][j];        
        }
    }

    int max = 0;
    for (int row = 1 ; row <= n ; ++row)
    {
        std::vector <std::pair <int,int>> v = split(row, 1, n);
        for (const auto &[colB, colE] : v)
        {
            auto [rowB, rowE] = extend(row, colB, colE);
            max = std::max(max, f(rowB, colB, rowE, colE) + (rowE - rowB + 1) * (colE - colB + 1));
        }
    }

    return max;
}

Compilation message (stderr)

soccer.cpp: In function 'std::pair<int, int> extend(int, int, int)':
soccer.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         mid = l + r >> 1;
      |               ~~^~~
soccer.cpp:35:28: warning: right operand of comma operator has no effect [-Wunused-value]
   35 |     l = row, r = n + 1, mid;
      |                            ^
soccer.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         mid = l + r >> 1;
      |               ~~^~~
soccer.cpp: In function 'int f(int, int, int, int)':
soccer.cpp:92:17: warning: unused variable 'lastRes' [-Wunused-variable]
   92 |             int lastRes = res;
      |                 ^~~~~~~
soccer.cpp:103:17: warning: unused variable 'lastRes' [-Wunused-variable]
  103 |             int lastRes = res;
      |                 ^~~~~~~

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