제출 #1271502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271502		rxlfd314	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	1343 ms	131456 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

int biggest_stadium(const int N, const vt<vt<int>> F) {
  vt<vt<ari2>> ranges(N);
  FOR(i, 0, N-1) {
    for (int j = 0, k; j < N; j++) {
      if (F[i][j])
        continue;
      for (k = j; k < N && !F[i][k]; k++);
      ranges[i].push_back({j, k-1});
      j = k;
    }
  }
  vt<vt<int>> psum(N+1, vt<int>(N+1));
  FOR(i, 0, N-1)
    FOR(j, 0, N-1)
      psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] - psum[i][j] + F[i][j];
  const auto query = [&](const int a, const int b, const int c, const int d) {
    return psum[c+1][d+1] - psum[a][d+1] - psum[c+1][b] + psum[a][b] == 0;
  };
  map<array<int, 4>, int> dp;
  const auto rec = [&](auto &&self, array<int, 4> state) -> int {
    auto &[l, r, u, d] = state;
    if (r < N - 1)
      ROF(i, 31 - __builtin_clz(N-1-r), 0)
        if (r + (1 << i) < N && query(r, u, r + (1 << i), d))
          r += 1 << i;
    if (l)
      ROF(i, 31 - __builtin_clz(l), 0)
        if (l >= (1 << i) && query(l - (1 << i), u, l, d))
          l -= 1 << i;
    if (dp.find(state) != dp.end())
      return dp[state];
    const auto progress = [&](const int new_row) {
      if (new_row < 0 || new_row >= N)
        return (r - l + 1) * (d - u + 1);
      const int s = max(lower_bound(all(ranges[new_row]), ari2{u + 1, -1}) - ranges[new_row].begin() - 1, 0l);
      const int e = lower_bound(all(ranges[new_row]), ari2{d + 1, -1}) - ranges[new_row].begin();
      const auto merge = [&](const ari2 &a, const ari2 &b) {
        return ari2{max(a[0], b[0]), min(a[1], b[1])};
      };
      int ret = (r - l + 1) * (d - u + 1);
      FOR(i, s, e-1) {
        const auto [uu, dd] = merge({u, d}, ranges[new_row][i]);
        if (uu <= dd)
          ret = max(ret, self(self, array<int, 4>{min(new_row, l), max(new_row, r), uu, dd}) + (r - l + 1) * (d - u + uu - dd));
      }
      return ret;
    };
    return dp[state] = max(progress(l - 1), progress(r + 1));
  };
  int ans = 0;
  FOR(i, 0, N-1)
    for (const auto &[l, r] : ranges[i])
      ans = max(ans, rec(rec, {i, i, l, r}));
  return ans;
}

• 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