oj.uz

Submission #1017076

# Submission time Handle Problem Language Result Execution time Memory
1017076 2024-07-08T20:21:55 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
28 / 100
 4500 ms 789436 KB 
#include "soccer.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 2005;
const int LOG = 12;
 
int n, a[MAX][MAX];
int L[MAX][MAX];
int R[MAX][MAX];
int U[MAX][MAX];
int D[MAX][MAX];
int go[MAX][MAX];
int logs[MAX];
int st_U[MAX][MAX][LOG];
int st_D[MAX][MAX][LOG];
int res;
map<array<int, 5>, bool> was;
 
int query_U(int i, int l, int r) {
  int k = logs[r - l + 1];
  return max(st_U[i][l][k], st_U[i][r - (1 << k) + 1][k]);
}
 
int query_D(int i, int l, int r) {
  int k = logs[r - l + 1];
  return min(st_D[i][l][k], st_D[i][r - (1 << k) + 1][k]);
}
 
void rec(int xl, int xr, int yl, int yr, int side, int cur) {
  if (was[{xl, xr, yl, yr, side}]) {
    return;
  }
  res = max(res, cur);
  was[{xl, xr, yl, yr, side}] = true;
  if (xl > 0) {
    // up
    int ptr = yl;
    while (ptr <= yr) {
      if (a[xl - 1][ptr] == 1) {
        ptr = go[xl - 1][ptr];
        continue;
      }
      int t = min(yr, R[xl - 1][ptr]);
      int new_x = query_U(xl - 1, ptr, t);
      if (ptr == yl && t == yr && ((yl > 0 && a[xl - 1][yl - 1] == 0) || (yr + 1 < n && a[xl - 1][yr + 1] == 0))) {
        ptr = R[xl - 1][ptr] + 1;
        continue;
      }
      rec(new_x, xr, ptr, t, 1, cur + (t - ptr + 1) * (xl - new_x));
      ptr = R[xl - 1][ptr] + 1;
    }
  }
  if (xr + 1 < n) {
    // down
    int ptr = yl;
    while (ptr <= yr) {
      if (a[xr + 1][ptr] == 1) {
        ptr = go[xr + 1][ptr];
        continue;
      }
      int t = min(yr, R[xr + 1][ptr]);
      int new_x = query_D(xr + 1, ptr, t);
      if (ptr == yl && t == yr && ((yl > 0 && a[xr + 1][yl - 1] == 0) || (yr + 1 < n && a[xr + 1][yr + 1] == 0))) {
        ptr = R[xr + 1][ptr] + 1;
        continue;
      } 
      rec(xl, new_x, ptr, t, 0, cur + (t - ptr + 1) * (new_x - xr));
      ptr = R[xr + 1][ptr] + 1;
    }
  }
}
 
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++) {
      a[i][j] = F[i][j];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[i][j] == 1) {
        continue;
      }
      int p = j;
      while (p + 1 < n && a[i][p + 1] == 0) {
        p += 1;
      }
      for (int k = j; k <= p; k++) {
        L[i][k] = j;
        R[i][k] = p;
      }
      j = p;
    }
  }
  for (int j = 0; j < n; j++) {
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 1) {
        continue;
      }
      int p = i;
      while (p + 1 < n && a[p + 1][j] == 0) {
        p += 1;
      }
      for (int k = i; k <= p; k++) {
        U[k][j] = i;
        D[k][j] = p;
      }
      i = p;
    }
  }
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      st_U[i][j][0] = U[i][j];
      st_D[i][j][0] = D[i][j];
    }
  }
  for (int k = 1; k < LOG; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j + (1 << k) <= n; j++) {
        st_U[i][j][k] = max(st_U[i][j][k - 1], st_U[i][j + (1 << (k - 1))][k - 1]);
        st_D[i][j][k] = min(st_D[i][j][k - 1], st_D[i][j + (1 << (k - 1))][k - 1]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = n - 1; j >= 0; j--) {
      if (a[i][j] == 1) {
        go[i][j] = (j == n - 1 ? n : go[i][j + 1]);
      } else {
        go[i][j] = j;
      }
    }
  }
  res = 0;
  vector<array<int, 4>> s;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[i][j] == 1) {
        continue;
      }
      if (j == 0 || a[i][j - 1] == 1) {
        s.push_back({R[i][j] - j + 1, i, j, R[i][j]});
      }
    }
  }
  sort(s.rbegin(), s.rend());
  for (auto& p : s) {
    int i = p[1];
    int l = p[2], r = p[3];
    rec(i, i, l, r, -1, r - l + 1);
  }
  return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB ok
2 Correct 2 ms 16732 KB ok
3 Correct 2 ms 16732 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 1 ms 14684 KB ok
6 Correct 2 ms 16732 KB ok
7 Correct 4 ms 37468 KB ok
8 Correct 31 ms 80396 KB ok
9 Correct 465 ms 503840 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
5.5 / 22.0

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

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB ok
2 Correct 2 ms 16732 KB ok
3 Correct 2 ms 16732 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16732 KB ok
6 Correct 2 ms 16732 KB ok
7 Correct 1 ms 16732 KB ok
8 Correct 2 ms 16728 KB ok
9 Correct 2 ms 16732 KB ok
10 Correct 2 ms 16732 KB ok
11 Correct 2 ms 16732 KB ok
12 Correct 1 ms 16732 KB ok
13 Correct 2 ms 16732 KB ok
14 Correct 2 ms 16732 KB ok
15 Correct 2 ms 16732 KB ok
16 Correct 2 ms 16732 KB ok
17 Correct 1 ms 16828 KB ok
18 Partially correct 2 ms 16732 KB partial
19 Partially correct 2 ms 16732 KB partial
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 16732 KB ok
25 Correct 1 ms 16732 KB ok
26 Correct 1 ms 16732 KB ok
27 Correct 2 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 2 ms 16732 KB ok
30 Correct 3 ms 25180 KB ok
31 Partially correct 3 ms 25180 KB partial
32 Correct 3 ms 24984 KB ok
33 Correct 3 ms 24924 KB ok
34 Correct 3 ms 24924 KB ok
35 Correct 3 ms 25072 KB ok
36 Correct 2 ms 24924 KB ok
37 Partially correct 3 ms 24924 KB partial
38 Correct 3 ms 24924 KB ok
39 Correct 3 ms 24924 KB ok
40 Correct 2 ms 24924 KB ok
41 Correct 3 ms 25180 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB ok
2 Correct 2 ms 16732 KB ok
3 Correct 2 ms 16732 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16732 KB ok
6 Correct 2 ms 16732 KB ok
7 Correct 1 ms 16732 KB ok
8 Correct 2 ms 16728 KB ok
9 Correct 2 ms 16732 KB ok
10 Correct 2 ms 16732 KB ok
11 Correct 2 ms 16732 KB ok
12 Correct 1 ms 16732 KB ok
13 Correct 2 ms 16732 KB ok
14 Correct 2 ms 16732 KB ok
15 Correct 2 ms 16732 KB ok
16 Correct 2 ms 16732 KB ok
17 Correct 1 ms 16828 KB ok
18 Partially correct 2 ms 16732 KB partial
19 Partially correct 2 ms 16732 KB partial
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 2 ms 16732 KB ok
23 Correct 2 ms 16732 KB ok
24 Correct 2 ms 16732 KB ok
25 Correct 1 ms 16732 KB ok
26 Correct 1 ms 16732 KB ok
27 Correct 2 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 2 ms 16732 KB ok
30 Correct 3 ms 25180 KB ok
31 Partially correct 3 ms 25180 KB partial
32 Correct 3 ms 24984 KB ok
33 Correct 3 ms 24924 KB ok
34 Correct 3 ms 24924 KB ok
35 Correct 3 ms 25072 KB ok
36 Correct 2 ms 24924 KB ok
37 Partially correct 3 ms 24924 KB partial
38 Correct 3 ms 24924 KB ok
39 Correct 3 ms 24924 KB ok
40 Correct 2 ms 24924 KB ok
41 Correct 3 ms 25180 KB ok
42 Partially correct 268 ms 111104 KB partial
43 Correct 176 ms 107780 KB ok
44 Partially correct 250 ms 119324 KB partial
45 Partially correct 185 ms 114584 KB partial
46 Partially correct 261 ms 116684 KB partial
47 Partially correct 42 ms 100176 KB partial
48 Correct 48 ms 99400 KB ok
49 Partially correct 48 ms 98384 KB partial
50 Partially correct 101 ms 105924 KB partial
51 Partially correct 99 ms 107956 KB partial
52 Partially correct 48 ms 97620 KB partial
53 Partially correct 37 ms 96584 KB partial
54 Partially correct 39 ms 97364 KB partial
55 Partially correct 78 ms 102588 KB partial
56 Correct 35 ms 97876 KB ok
57 Correct 117 ms 113388 KB ok
58 Correct 123 ms 114464 KB ok
59 Correct 142 ms 117584 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB ok
2 Correct 2 ms 16732 KB ok
3 Correct 2 ms 16732 KB ok
4 Correct 2 ms 16732 KB ok
5 Correct 2 ms 16732 KB ok
6 Correct 1 ms 14684 KB ok
7 Correct 2 ms 16732 KB ok
8 Correct 4 ms 37468 KB ok
9 Correct 31 ms 80396 KB ok
10 Correct 465 ms 503840 KB ok
11 Correct 2 ms 16732 KB ok
12 Correct 1 ms 16732 KB ok
13 Correct 2 ms 16728 KB ok
14 Correct 2 ms 16732 KB ok
15 Correct 2 ms 16732 KB ok
16 Correct 2 ms 16732 KB ok
17 Correct 1 ms 16732 KB ok
18 Correct 2 ms 16732 KB ok
19 Correct 2 ms 16732 KB ok
20 Correct 2 ms 16732 KB ok
21 Correct 2 ms 16732 KB ok
22 Correct 1 ms 16828 KB ok
23 Partially correct 2 ms 16732 KB partial
24 Partially correct 2 ms 16732 KB partial
25 Correct 2 ms 16732 KB ok
26 Correct 2 ms 16732 KB ok
27 Correct 2 ms 16732 KB ok
28 Correct 2 ms 16732 KB ok
29 Correct 2 ms 16732 KB ok
30 Correct 1 ms 16732 KB ok
31 Correct 1 ms 16732 KB ok
32 Correct 2 ms 16732 KB ok
33 Correct 2 ms 16732 KB ok
34 Correct 2 ms 16732 KB ok
35 Correct 3 ms 25180 KB ok
36 Partially correct 3 ms 25180 KB partial
37 Correct 3 ms 24984 KB ok
38 Correct 3 ms 24924 KB ok
39 Correct 3 ms 24924 KB ok
40 Correct 3 ms 25072 KB ok
41 Correct 2 ms 24924 KB ok
42 Partially correct 3 ms 24924 KB partial
43 Correct 3 ms 24924 KB ok
44 Correct 3 ms 24924 KB ok
45 Correct 2 ms 24924 KB ok
46 Correct 3 ms 25180 KB ok
47 Partially correct 268 ms 111104 KB partial
48 Correct 176 ms 107780 KB ok
49 Partially correct 250 ms 119324 KB partial
50 Partially correct 185 ms 114584 KB partial
51 Partially correct 261 ms 116684 KB partial
52 Partially correct 42 ms 100176 KB partial
53 Correct 48 ms 99400 KB ok
54 Partially correct 48 ms 98384 KB partial
55 Partially correct 101 ms 105924 KB partial
56 Partially correct 99 ms 107956 KB partial
57 Partially correct 48 ms 97620 KB partial
58 Partially correct 37 ms 96584 KB partial
59 Partially correct 39 ms 97364 KB partial
60 Partially correct 78 ms 102588 KB partial
61 Correct 35 ms 97876 KB ok
62 Correct 117 ms 113388 KB ok
63 Correct 123 ms 114464 KB ok
64 Correct 142 ms 117584 KB ok
65 Execution timed out 4583 ms 789436 KB Time limit exceeded
66 Halted 0 ms 0 KB -