Submission #1240637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240637		mychecksedad	Soccer Stadium (IOI23_soccer)	C++17	34.50 / 100	14 ms	4936 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 = 35, M = 3e5;

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;  
      // cerr << i << ' ' << L << ' ' << R << ":\n";

      // we know l...r borders
      for(int u = i; u >= 0; --u){
        for(int d = i; d < n; ++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] = 0;
                continue;
              }
              if(u == i){
                dp[u][d][l][r][0] = 0;
                dp[u][d][l][r][1] = max({
                  dp[u][d - 1][l][r][1] + len,
                  l > L ? dp[u][d][l - 1][r][1] : 0,
                  r < R ? dp[u][d][l][r + 1][1] : 0,
                });
              }else if(d == i){
                dp[u][d][l][r][1] = 0;
                dp[u][d][l][r][0] = max({
                  dp[u + 1][d][l][r][0] + len,
                  l > L ? dp[u][d][l - 1][r][0] : 0,
                  r < R ? dp[u][d][l][r + 1][0] : 0,
                });
              }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] : 0,
                  r < R ? dp[u][d][l][r + 1][0] : 0,
                });

                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] : 0,
                  r < R ? dp[u][d][l][r + 1][1] : 0,
                });
              }            
              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: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30