제출 #841909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841909		flashmt	Soccer Stadium (IOI23_soccer)	C++17	61 / 100	348 ms	47952 KiB

soccer

#include "soccer.h"
// #include "Debug.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 33;

int f[N][N][N][N];

int isBad(vector<pair<int, int>> a)
{
  int len = size(a);
  for (int i = 0; i < len; i++)
    for (int j = i + 1; j < len; j++)
    {
      auto [l, r] = a[i];
      auto [ll, rr] = a[j];
      int intersect = min(r, rr) - max(l, ll);
      if (intersect >= 0 && intersect < min(r - l, rr - ll))
        return 1;
    }
  return 0;
}

void update(int &x, int y)
{
  x = max(x, y);
}

int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
  int area = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      area += 1 - a[i][j];

  int canUseAll = 1;

  vector<vector<pair<int, int>>> rows(n);
  vector<pair<int, int>> allRows;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n;)
      if (a[i][j]) j++;
      else
      {
        int jj = j + 1;
        while (jj < n && !a[i][jj])
          jj++;
        rows[i].push_back({j, jj - 1});
        j = jj;
      }

    if (size(rows[i]) > 1) canUseAll = 0;
    else if (size(rows[i]) == 1) allRows.push_back(rows[i][0]);
  }

  vector<vector<pair<int, int>>> cols(n);
  vector<pair<int, int>> allCols;
  for (int j = 0; j < n; j++)
  {
    for (int i = 0; i < n;)
      if (a[i][j]) i++;
      else
      {
        int ii = i + 1;
        while (ii < n && !a[ii][j])
          ii++;
        cols[j].push_back({i, ii - 1});
        i = ii;
      }

    if (size(cols[j]) > 1) canUseAll = 0;
    else if (size(cols[j]) == 1) allCols.push_back(cols[j][0]);
  }

  canUseAll &= !isBad(allRows) && !isBad(allCols);
  if (canUseAll)
    return area;

  if (n <= N)
  {
    for (int i = 0; i < n; i++)
      for (auto [l, r] : rows[i])
        f[i][i][l][r] = r - l + 1;

    int ans = 0;
    for (int len = 1; len < n; len++)
      for (int i = 0; i + len <= n; i++)
        for (int j = 0; j < n; j++)
          for (int jj = j; jj < n; jj++)
          {
            int ii = i + len - 1;
            if (!f[i][ii][j][jj])
              continue;

            ans = max(ans, f[i][ii][j][jj]);

            if (i)
            {
              for (auto [l, r] : rows[i - 1])
              {
                int k = max(j, l), kk = min(jj, r);
                if (k <= kk)
                  update(f[i - 1][ii][k][kk], f[i][ii][j][jj] + kk - k + 1);
              }
            }

            if (ii + 1 < n)
            {
              for (auto [l, r] : rows[ii + 1])
              {
                int k = max(j, l), kk = min(jj, r);
                if (k <= kk)
                  update(f[i][ii + 1][k][kk], f[i][ii][j][jj] + kk - k + 1);
              }
            }
          }

    for (int j = 0; j < n; j++)
      for (int jj = j; jj < n; jj++)
        ans = max(ans, f[0][n - 1][j][jj]);

    return ans;
  }

  return 0;
}

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