Submission #1240812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240812		mychecksedad	Soccer Stadium (IOI23_soccer)	C++17	7.50 / 100	8 ms	7748 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
// #define cerr if(0) cerr
const int N = 50, M = 3e5;
const int INF = 1e6;

int arr[4][2] = {
  {0, 1},
  {0, -1},
  {1, 0},
  {-1, 0}
};
int dp[N][N][N][N][2], pref[N][N];
bitset<N> vis[N];
vector<pii> g[N][N];

int get(int row, int l, int r){
  return pref[row][r] - (l == 0 ? 0 : pref[row][l - 1]);
}

int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
  int cnt = 0, px = 0, py = 0;
  queue<pii> q;
  bool any = false;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i][j] == 0){
        if(!any){
          any = true;
          q.push({i, j});
          vis[i][j] = 1;
        }
        for(int k = 0; k < 4; ++k){
          int nx = i + arr[k][0];
          int ny = j + arr[k][1];
          if(nx >= 0 && ny < n && ny >= 0 && nx < n && a[nx][ny] == 0){
            g[i][j].pb({nx, ny});
          }
        }
      }else{
        ++cnt;
        px = i, py = j;
      }
    }
  }
  if(cnt == 0){
    return n * n;
  }
  if(cnt == 1){
    return n*n - min({
      (px + 1) * (py + 1),
      (px + 1) * (n - py),
      (n - px) * (n - py),
      (n - px) * (py + 1),
    });
  }
  int ans = 0;

  for(int i = 0; i < n; ++i){
    pref[i][0] = a[i][0];
    for(int j = 1; j < n; ++j) pref[i][j] = pref[i][j - 1] + a[i][j];
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(a[i][j]) continue;
      int L = j;
      while(j < n && a[i][j] == 0) ++j;
      --j;
      int R = j;  
      assert(!get(i, L, R));
      // cerr << i << ' ' << L << ' ' << R << ":\n";

      int limu = 0;
      int limd = n;
      for(int u = i - 1; u >= 0; --u){
        if(get(u, L, R) == R - L + 1){
          limu = u + 1;
          break;
        }
      }
      for(int d = i + 1; d < n; ++d){
        if(get(d, L, R) == R - L + 1){
          if(L > 0 && get(d, L - 1, R) == R - L + 2){
            limd = d - 1;
            break;
          }
          if(R + 1 < n && get(d, L, R + 1) == R - L + 2){
            limd = d - 1;
            break;
          }
        }
      }
      

      // we know l...r borders

      for(int u = i; u >= limu; --u){
        for(int d = i; d < limd; ++d){
          for(int len = R-L+1; len >= 1; --len){
            for(int l = L; l + len - 1 <= R; ++l){
              int r = l + len - 1;
              if(u == i && d == i){
                dp[u][d][l][r][0] = dp[u][d][l][r][1] = R-L+1;
                ans = max(ans, len);
                continue;
              }
              if(get(u, l, r) || get(d, l, r)){
                dp[u][d][l][r][0] = dp[u][d][l][r][1] = -INF;
                continue;
              }
              if(u == i){
                dp[u][d][l][r][0] = -INF;
                dp[u][d][l][r][1] = max({
                  dp[u][d - 1][l][r][1] + len,
                  l > L ? dp[u][d][l - 1][r][1] : -INF,
                  r < R ? dp[u][d][l][r + 1][1] : -INF,
                });
              }else if(d == i){
                dp[u][d][l][r][1] = -INF;
                dp[u][d][l][r][0] = max({
                  dp[u + 1][d][l][r][0] + len,
                  l > L ? dp[u][d][l - 1][r][0] : -INF,
                  r < R ? dp[u][d][l][r + 1][0] : -INF,
                });
              }else{
                dp[u][d][l][r][0] = max({
                  dp[u + 1][d][l][r][0] + len,
                  dp[u + 1][d][l][r][1] + len,
                  l > L ? dp[u][d][l - 1][r][0] : -INF,
                  r < R ? dp[u][d][l][r + 1][0] : -INF,
                });

                dp[u][d][l][r][1] = max({
                  dp[u][d - 1][l][r][0] + len,
                  dp[u][d - 1][l][r][1] + len,
                  l > L ? dp[u][d][l - 1][r][1] : -INF,
                  r < R ? dp[u][d][l][r + 1][1] : -INF,
                });
              }            
              ans = max({
                ans,
                dp[u][d][l][r][0],
                dp[u][d][l][r][1]
              });
              // cerr << u << ' ' << d << ' ' << l << ' ' << r << ' ' << dp[u][d][l][r][0] << ' ' << dp[u][d][l][r][1] << '\n';
            }
            // cerr << '\n';
          }
          // cerr << '\n';
        }
      }
      // cerr << '\n';
      // cerr << '\n';
    }
  }


  return ans;
}

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