oj.uz

Submission #843079

# Submission time Handle Problem Language Result Execution time Memory
843079 2023-09-03T15:55:13 Z flashmt Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 735092 KB 
#include "soccer.h"
// #include "Debug.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2020;

map<int, int> f[N][N];

int isBad(vector<pair<int, int>> a)
{
  int len = size(a);
  for (int i = 0; i < len; i++)
    for (int j = i + 1; j < len; j++)
    {
      auto [l, r] = a[i];
      auto [ll, rr] = a[j];
      int intersect = min(r, rr) - max(l, ll);
      if (intersect >= 0 && intersect < min(r - l, rr - ll))
        return 1;
    }
  return 0;
}

int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
  int area = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      area += 1 - a[i][j];

  if (area == n * n - 1)
  {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (a[i][j])
        {
          int exclude = min(i + 1, n - i) * min(j + 1, n - j);
          return n * n - exclude;
        }
  }

  int canUseAll = 1;

  vector<vector<pair<int, int>>> rows(n);
  vector<pair<int, int>> allRows;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n;)
      if (a[i][j]) j++;
      else
      {
        int jj = j + 1;
        while (jj < n && !a[i][jj])
          jj++;
        rows[i].push_back({j, jj - 1});
        j = jj;
      }

    if (size(rows[i]) > 1) canUseAll = 0;
    else if (size(rows[i]) == 1) allRows.push_back(rows[i][0]);
  }

  vector<vector<pair<int, int>>> cols(n);
  vector<pair<int, int>> allCols;
  for (int j = 0; j < n; j++)
  {
    for (int i = 0; i < n;)
      if (a[i][j]) i++;
      else
      {
        int ii = i + 1;
        while (ii < n && !a[ii][j])
          ii++;
        cols[j].push_back({i, ii - 1});
        i = ii;
      }

    if (size(cols[j]) > 1) canUseAll = 0;
    else if (size(cols[j]) == 1) allCols.push_back(cols[j][0]);
  }

  canUseAll &= !isBad(allRows) && !isBad(allCols);
  if (canUseAll)
    return area;

  for (int i = 0; i < n; i++)
    for (auto [l, r] : rows[i])
      f[i][i][l * N + r] = r - l + 1;

  int ans = 0;
  for (int len = 1; len < n; len++)
    for (int i = 0; i + len <= n; i++)
    {
      int ii = i + len - 1;
      for (auto [u, v] : f[i][ii])
      {
        int j = u / N, jj = u % N;
        ans = max(ans, v);

        if (i)
        {
          for (auto [l, r] : rows[i - 1])
          {
            int k = max(j, l), kk = min(jj, r);
            int uu = k * N + kk;
            if (k <= kk)
              f[i - 1][ii][uu] = max(f[i - 1][ii][uu], v + kk - k + 1);
          }
        }

        if (ii + 1 < n)
        {
          for (auto [l, r] : rows[ii + 1])
          {
            int k = max(j, l), kk = min(jj, r);
            int uu = k * N + kk;
            if (k <= kk)
              f[i][ii + 1][uu] = max(f[i][ii + 1][uu], v + kk - k + 1);
          }
        }
      }
    }

  for (auto [_, v] : f[0][n - 1])
      ans = max(ans, v);

  return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 191996 KB ok
2 Correct 36 ms 191824 KB ok
3 Correct 38 ms 191856 KB ok
4 Correct 37 ms 191836 KB ok
5 Correct 42 ms 191828 KB ok
6 Correct 38 ms 191892 KB ok
7 Correct 39 ms 192084 KB ok
8 Correct 54 ms 193804 KB ok
9 Correct 273 ms 223308 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 191996 KB ok
2 Correct 36 ms 191824 KB ok
3 Correct 40 ms 191836 KB ok
4 Correct 37 ms 191908 KB ok
5 Correct 37 ms 191824 KB ok
6 Correct 36 ms 191864 KB ok
7 Correct 40 ms 191828 KB ok
8 Correct 36 ms 191856 KB ok
9 Correct 36 ms 191824 KB ok
10 Correct 37 ms 191848 KB ok
11 Correct 37 ms 191824 KB ok
12 Correct 37 ms 191912 KB ok
13 Correct 42 ms 191828 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 191824 KB ok
2 Correct 42 ms 191996 KB ok
3 Correct 36 ms 191824 KB ok
4 Correct 40 ms 191836 KB ok
5 Correct 37 ms 191908 KB ok
6 Correct 37 ms 191824 KB ok
7 Correct 36 ms 191864 KB ok
8 Correct 40 ms 191828 KB ok
9 Correct 36 ms 191856 KB ok
10 Correct 36 ms 191824 KB ok
11 Correct 37 ms 191848 KB ok
12 Correct 37 ms 191824 KB ok
13 Correct 37 ms 191912 KB ok
14 Correct 42 ms 191828 KB ok
15 Correct 43 ms 191836 KB ok
16 Correct 38 ms 191832 KB ok
17 Correct 37 ms 191836 KB ok
18 Correct 41 ms 191828 KB ok
19 Correct 37 ms 191824 KB ok
20 Correct 37 ms 191828 KB ok
21 Correct 43 ms 191824 KB ok
22 Correct 36 ms 191860 KB ok
23 Correct 36 ms 191964 KB ok
24 Correct 37 ms 191832 KB ok
25 Correct 37 ms 191828 KB ok
26 Correct 37 ms 191828 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 191824 KB ok
2 Correct 42 ms 191996 KB ok
3 Correct 36 ms 191824 KB ok
4 Correct 38 ms 191856 KB ok
5 Correct 37 ms 191836 KB ok
6 Correct 40 ms 191836 KB ok
7 Correct 37 ms 191908 KB ok
8 Correct 37 ms 191824 KB ok
9 Correct 36 ms 191864 KB ok
10 Correct 40 ms 191828 KB ok
11 Correct 36 ms 191856 KB ok
12 Correct 36 ms 191824 KB ok
13 Correct 37 ms 191848 KB ok
14 Correct 37 ms 191824 KB ok
15 Correct 37 ms 191912 KB ok
16 Correct 42 ms 191828 KB ok
17 Correct 43 ms 191836 KB ok
18 Correct 38 ms 191832 KB ok
19 Correct 37 ms 191836 KB ok
20 Correct 41 ms 191828 KB ok
21 Correct 37 ms 191824 KB ok
22 Correct 37 ms 191828 KB ok
23 Correct 43 ms 191824 KB ok
24 Correct 36 ms 191860 KB ok
25 Correct 36 ms 191964 KB ok
26 Correct 37 ms 191832 KB ok
27 Correct 37 ms 191828 KB ok
28 Correct 37 ms 191828 KB ok
29 Correct 36 ms 191996 KB ok
30 Correct 37 ms 192128 KB ok
31 Correct 39 ms 191932 KB ok
32 Correct 37 ms 191952 KB ok
33 Correct 42 ms 192092 KB ok
34 Correct 42 ms 191968 KB ok
35 Correct 36 ms 191836 KB ok
36 Correct 36 ms 191824 KB ok
37 Correct 41 ms 191820 KB ok
38 Correct 37 ms 191864 KB ok
39 Correct 36 ms 192092 KB ok
40 Correct 36 ms 192092 KB ok
41 Correct 36 ms 192084 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 191824 KB ok
2 Correct 42 ms 191996 KB ok
3 Correct 36 ms 191824 KB ok
4 Correct 38 ms 191856 KB ok
5 Correct 37 ms 191836 KB ok
6 Correct 40 ms 191836 KB ok
7 Correct 37 ms 191908 KB ok
8 Correct 37 ms 191824 KB ok
9 Correct 36 ms 191864 KB ok
10 Correct 40 ms 191828 KB ok
11 Correct 36 ms 191856 KB ok
12 Correct 36 ms 191824 KB ok
13 Correct 37 ms 191848 KB ok
14 Correct 37 ms 191824 KB ok
15 Correct 37 ms 191912 KB ok
16 Correct 42 ms 191828 KB ok
17 Correct 43 ms 191836 KB ok
18 Correct 38 ms 191832 KB ok
19 Correct 37 ms 191836 KB ok
20 Correct 41 ms 191828 KB ok
21 Correct 37 ms 191824 KB ok
22 Correct 37 ms 191828 KB ok
23 Correct 43 ms 191824 KB ok
24 Correct 36 ms 191860 KB ok
25 Correct 36 ms 191964 KB ok
26 Correct 37 ms 191832 KB ok
27 Correct 37 ms 191828 KB ok
28 Correct 37 ms 191828 KB ok
29 Correct 36 ms 191996 KB ok
30 Correct 37 ms 192128 KB ok
31 Correct 39 ms 191932 KB ok
32 Correct 37 ms 191952 KB ok
33 Correct 42 ms 192092 KB ok
34 Correct 42 ms 191968 KB ok
35 Correct 36 ms 191836 KB ok
36 Correct 36 ms 191824 KB ok
37 Correct 41 ms 191820 KB ok
38 Correct 37 ms 191864 KB ok
39 Correct 36 ms 192092 KB ok
40 Correct 36 ms 192092 KB ok
41 Correct 36 ms 192084 KB ok
42 Correct 433 ms 247804 KB ok
43 Correct 271 ms 220592 KB ok
44 Correct 1852 ms 596064 KB ok
45 Correct 2231 ms 735092 KB ok
46 Correct 738 ms 315472 KB ok
47 Correct 142 ms 229712 KB ok
48 Correct 53 ms 193872 KB ok
49 Correct 66 ms 199324 KB ok
50 Execution timed out 4562 ms 632000 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 191824 KB ok
2 Correct 42 ms 191996 KB ok
3 Correct 36 ms 191824 KB ok
4 Correct 38 ms 191856 KB ok
5 Correct 37 ms 191836 KB ok
6 Correct 42 ms 191828 KB ok
7 Correct 38 ms 191892 KB ok
8 Correct 39 ms 192084 KB ok
9 Correct 54 ms 193804 KB ok
10 Correct 273 ms 223308 KB ok
11 Correct 40 ms 191836 KB ok
12 Correct 37 ms 191908 KB ok
13 Correct 37 ms 191824 KB ok
14 Correct 36 ms 191864 KB ok
15 Correct 40 ms 191828 KB ok
16 Correct 36 ms 191856 KB ok
17 Correct 36 ms 191824 KB ok
18 Correct 37 ms 191848 KB ok
19 Correct 37 ms 191824 KB ok
20 Correct 37 ms 191912 KB ok
21 Correct 42 ms 191828 KB ok
22 Correct 43 ms 191836 KB ok
23 Correct 38 ms 191832 KB ok
24 Correct 37 ms 191836 KB ok
25 Correct 41 ms 191828 KB ok
26 Correct 37 ms 191824 KB ok
27 Correct 37 ms 191828 KB ok
28 Correct 43 ms 191824 KB ok
29 Correct 36 ms 191860 KB ok
30 Correct 36 ms 191964 KB ok
31 Correct 37 ms 191832 KB ok
32 Correct 37 ms 191828 KB ok
33 Correct 37 ms 191828 KB ok
34 Correct 36 ms 191996 KB ok
35 Correct 37 ms 192128 KB ok
36 Correct 39 ms 191932 KB ok
37 Correct 37 ms 191952 KB ok
38 Correct 42 ms 192092 KB ok
39 Correct 42 ms 191968 KB ok
40 Correct 36 ms 191836 KB ok
41 Correct 36 ms 191824 KB ok
42 Correct 41 ms 191820 KB ok
43 Correct 37 ms 191864 KB ok
44 Correct 36 ms 192092 KB ok
45 Correct 36 ms 192092 KB ok
46 Correct 36 ms 192084 KB ok
47 Correct 433 ms 247804 KB ok
48 Correct 271 ms 220592 KB ok
49 Correct 1852 ms 596064 KB ok
50 Correct 2231 ms 735092 KB ok
51 Correct 738 ms 315472 KB ok
52 Correct 142 ms 229712 KB ok
53 Correct 53 ms 193872 KB ok
54 Correct 66 ms 199324 KB ok
55 Execution timed out 4562 ms 632000 KB Time limit exceeded
56 Halted 0 ms 0 KB -