제출 #843079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843079		flashmt	축구 경기장 (IOI23_soccer)	C++17	54 / 100	4562 ms	735092 KiB

soccer

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

map<int, int> f[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;
}

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];

  if (area == n * n - 1)
  {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (a[i][j])
        {
          int exclude = min(i + 1, n - i) * min(j + 1, n - j);
          return n * n - exclude;
        }
  }

  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;

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

  int ans = 0;
  for (int len = 1; len < n; len++)
    for (int i = 0; i + len <= n; i++)
    {
      int ii = i + len - 1;
      for (auto [u, v] : f[i][ii])
      {
        int j = u / N, jj = u % N;
        ans = max(ans, v);

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

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

  for (auto [_, v] : f[0][n - 1])
      ans = max(ans, v);

  return ans;
}

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