oj.uz

Submission #1037452

# Submission time Handle Problem Language Result Execution time Memory
1037452 2024-07-28T22:33:07 Z aaaaaarroz Soccer Stadium (IOI23_soccer) C++17
30 / 100
 4500 ms 5264 KB 
#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int biggest_stadium(int N, vector<vector<int>> F) {
  int n = N;
  vector<vector<int>> a = F, next(n, vector<int>(n)), sum(n, vector<int>(n));
  function<int(int, int, int, int)> summ = [&] (int l, int r, int x, int y) {
    long long ans = sum[y][r];
    if (x - 1 >= 0) ans -= sum[x - 1][r];
    if (l - 1 >= 0) ans -= sum[y][l - 1];
    if (x - 1 >= 0 && l - 1 >= 0) ans += sum[x - 1][l - 1];
    return ans;
  };
  function<int(int, int, int, int)> f = [&] (int l, int r, int x, int y) {
    int ans = 0;
    if (x - 1 >= 0) {
      for (int j = l; j <= r; j ++) {
        if (a[x - 1][j]) continue;
        int z = min(r, next[x - 1][j]);
        ans = max(ans, f(j, z, x - 1, y) + z - j + 1);
        j = z;
      }
    }
    if (y + 1 < n) {
      for (int j = l; j <= r; j ++) {
        if (a[y + 1][j]) continue;
        int z = min(r, next[y + 1][j]);
        int ll = y + 1, rr = n, mid;
        while (ll < rr) {
          mid = (ll + rr) / 2;
          if (summ(j, z, x, mid) == 0) ll = mid + 1;
          else rr = mid;
        }
        ll --;
        ans = max(ans, f(j, z, x, ll) + (z - j + 1) * (ll - y));
        j = z;
      }
    }

    return ans;
  };
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < n; j ++) {
      sum[i][j] += a[i][j];
      if (j) sum[i][j] += sum[i][j - 1];
    }
  }
  for (int i = 1; i < n; i ++) {
    for (int j = 0; j < n; j ++) sum[i][j] += sum[i - 1][j];
  }
  for (int i = 0; i < n; i ++) {
    if (a[i][n - 1] == 0) next[i][n - 1] = n - 1;
    else next[i][n - 1] = n - 2;
    for (int j = n - 2; j >= 0; j --) {
      if (a[i][j]) next[i][j] = j - 1;
      else next[i][j] = next[i][j + 1];
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < n; j ++) {
      if (a[i][j]) continue;
      ans = max(ans, f(j, next[i][j], i, i) + next[i][j] - j + 1);
      j = next[i][j];
    }
  }
  return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 428 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 8 ms 604 KB ok
8 Execution timed out 4589 ms 5264 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 344 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 428 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 1 ms 344 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 7 ms 452 KB ok
36 Correct 1 ms 448 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 4 ms 348 KB ok
39 Correct 19 ms 348 KB ok
40 Correct 6 ms 344 KB ok
41 Execution timed out 4595 ms 348 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 428 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 1 ms 344 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 1 ms 348 KB ok
31 Correct 1 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 7 ms 452 KB ok
36 Correct 1 ms 448 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 4 ms 348 KB ok
39 Correct 19 ms 348 KB ok
40 Correct 6 ms 344 KB ok
41 Execution timed out 4595 ms 348 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 428 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 8 ms 604 KB ok
9 Execution timed out 4589 ms 5264 KB Time limit exceeded
10 Halted 0 ms 0 KB -