Submission #1206552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206552		hyakup	Soccer Stadium (IOI23_soccer)	C++20	54 / 100	226 ms	31900 KiB

soccer

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

int check_all( vector<vector<int>> &mat ){
  int n = mat.size();
  vector<int> l(n, n), r(n, -1);
  int tot = 0;
  for( int i = 0; i < n; i++ )
    for( int j = 0; j < n; j++ ) if( mat[i][j] == 0 ){
      tot++;
      l[i] = min( l[i], j );
      r[i] = max( r[i], j );
    }

  return tot;

  auto contains = [&]( int a, int b ){
    return l[a] <= l[b] && r[b] <= r[a];
  };

  int cont = 0;
  for( int i = 0; i < n; i++ ) if( l[i] != n ){
    cont += (r[i] - l[i] + 1);
    for( int j = i + 1; j < n; j++ ) if( l[j] != n && !contains( i, j ) && !contains( j, i ) ) return 0;
  }

  if( tot < cont ) return 0;

  fill( l.begin(), l.end(), n );
  fill( r.begin(), r.end(), -1 );

  for( int i = 0; i < n; i++ )
    for( int j = 0; j < n; j++ ) if( mat[j][i] == 0 ){
      l[i] = min( l[i], j );
      r[i] = max( r[i], j );
    }

  cont = 0;
  for( int i = 0; i < n; i++ ) if( l[i] != n ){
    cont += (r[i] - l[i] + 1);
    for( int j = i + 1; j < n; j++ ) if( l[j] != n && !contains( i, j ) && !contains( j, i ) ) return 0;
  }

  if( tot < cont ) return 0;

  return tot;
}

const int maxn = 50;
const int inf = 1e5;
int dp[maxn][maxn][maxn][maxn];
int sum[maxn][maxn];
int n;

int query( int l, int r, int u, int d ){
  return sum[d][r] - sum[d][l - 1] - sum[u - 1][r] + sum[u - 1][l - 1];
}

int solve( int l, int r, int u, int d ){
  if( l < 0 || r >= n || u < 0 || d >= n ) return -inf;
  if( u > d ) return 0;

  if( query( l + 1, r + 1, u + 1, d + 1 ) ) return -inf;
  if( dp[l][r][u][d] != -1 ) return dp[l][r][u][d];

  dp[l][r][u][d] = max({ solve( l - 1, r, u, d ) + (d - u + 1),
                        solve( l, r + 1, u, d ) + (d - u + 1),
                        solve( l, r, u + 1, d ),
                        solve( l, r, u, d - 1 ) });

  return dp[l][r][u][d];
}

int solve1( vector<vector<int>> &mat ){
  int n = mat.size();
  int a, b;
  for( int i = 0; i < n; i++ ) for(int j = 0; j < n; j++ ) if( mat[i][j] == 1 ) a = i, b = j;
  return n*n - min( a + 1, n - a )*min( b + 1, n - b );
}

int biggest_stadium(int N, vector<vector<int>> mat ){

  int total = check_all(mat);
  if( total + 1 == N*N ) return solve1(mat);

  n = N;

  for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) for( int k = 0; k < n; k++ ) for( int l = 0; l < n; l++ ) dp[i][j][k][l] = -1;
  for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ )
    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];

  int resp = 0;
  vector<int> h(n);
  for( int i = 0; i < n; i++ ){
    for( int j = 0; j < n; j++ ){
      if( mat[i][j] == 0 ) h[j]++;
      else h[j] = 0;
      resp = max( resp, solve( j, j, i - h[j] + 1, i ) + h[j] );
    }
  }

  return resp;
}

• 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