Submission #841850

#	Time	Username	Problem	Language	Result	Execution time	Memory
841850		flashmt	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	308 ms	31908 KiB

soccer

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

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

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

  if (isBad(rows))
    return 0;

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

  if (isBad(cols))
    return 0;

  return area;
}

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