oj.uz

Submission #1071891

# Submission time Handle Problem Language Result Execution time Memory
1071891 2024-08-23T12:10:21 Z KaleemRazaSyed Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 133972 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 3 ms 13148 KB ok
8 Correct 124 ms 34756 KB ok
9 Execution timed out 4556 ms 133972 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 2 ms 8540 KB ok
6 Partially correct 1 ms 8540 KB partial
7 Incorrect 1 ms 8540 KB wrong
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 2 ms 8540 KB ok
7 Partially correct 1 ms 8540 KB partial
8 Incorrect 1 ms 8540 KB wrong
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 2 ms 8540 KB ok
9 Partially correct 1 ms 8540 KB partial
10 Incorrect 1 ms 8540 KB wrong
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 2 ms 8540 KB ok
9 Partially correct 1 ms 8540 KB partial
10 Incorrect 1 ms 8540 KB wrong
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB ok
2 Correct 1 ms 8540 KB ok
3 Correct 1 ms 8540 KB ok
4 Correct 1 ms 8540 KB ok
5 Correct 1 ms 8540 KB ok
6 Correct 1 ms 8540 KB ok
7 Correct 1 ms 8540 KB ok
8 Correct 3 ms 13148 KB ok
9 Correct 124 ms 34756 KB ok
10 Execution timed out 4556 ms 133972 KB Time limit exceeded
11 Halted 0 ms 0 KB -