Submission #1071891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071891		KaleemRazaSyed	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	4556 ms	133972 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

const int N = 2000 + 5;
int n, pref[N][N], l[N][N], r[N][N], u[N][N], d[N][N], f[N][N];

void precompute()
{
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < n; j++)
      l[i][j] = r[i][j] = u[i][j] = d[i][j] = 1 - f[i][j] ;

  for(int i = 0; i < n; i ++)
    for(int j = 1; j < n; j ++)
      if(l[i][j])
	l[i][j] += l[i][j - 1];
  
  for(int i = 0; i < n; i ++)
    for(int j = n - 2; j >= 0; j --)
      if(r[i][j])
	r[i][j] += r[i][j + 1];

  for(int i = 1; i < n; i ++)
    for(int j = 0; j < n; j ++)
      if(u[i][j])
	u[i][j] += u[i - 1][j];

  for(int i = n - 2; i >= 0; i --)
    for(int j = 0; j < n; j ++)
      if(d[i][j])
	d[i][j] += d[i + 1][j];

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

int extract(int idx)
{

  vector<int> a, b;
  
  for(int i = 0; i < n; i++)
    a.push_back(u[idx][i]), b.push_back(d[idx][i] - 1);

  int fans = 0;
  for(int p = 0; p < n; p ++)
    {
      int ans = a[p] + b[p];
      int x1 = a[p], x2 = b[p];
      for(int j = p - 1; j >= 0; j --)
	{
	  x1 = min(x1, a[j]);
	  x2 = min(x2, b[j]);
	  ans += x1 + x2;
	}
      x1 = a[p], x2 = b[p];
      for(int j = p + 1; j < n; j++)
	{
	  x1 = min(x1, a[j]);
	  x2 = min(x2, b[j]);
	  ans += x1 + x2;
	}
      fans = max(fans, ans);
    }
  return fans;
}

int biggest_stadium(int N, vector<vector<int> > F)
{
  n = N;

  for(int i = 0; i < n; i ++)
    for(int j = 0; j < n; j ++)
      f[i][j] = F[i][j];

  precompute();
  int ans = 0;
  for(int i = 0; i < n; i ++)
    ans = max(ans, extract(i));  

  return ans;
}

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