oj.uz

Submission #1017081

# Submission time Handle Problem Language Result Execution time Memory
1017081 2024-07-08T20:27:01 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 739800 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 sum[MAX][MAX];
int logs[MAX];
int st_U[MAX][MAX][LOG];
int st_D[MAX][MAX][LOG];
int res;
map<array<int, 5>, int> mp;
 
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]);
}

int get_sum(int i, int l, int r) {
  return sum[i][r] - (l == 0 ? 0 : sum[i][l - 1]);
}
 
void rec(int xl, int xr, int yl, int yr, int side, int cur) {
  if (mp[{xl, xr, yl, yr, side}] >= cur) {
    return;
  }
  res = max(res, cur);
  mp[{xl, xr, yl, yr, side}] = cur;
  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_xl = 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;
      }
      int new_xr = ((xr == n - 1 || get_sum(xr + 1, ptr, t) > 0) ? xr : query_D(xr + 1, ptr, t));
      rec(new_xl, new_xr, ptr, t, 1, cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr));
      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_xr = 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;
      } 
      int new_xl = xl;

      rec(xl, new_xr, ptr, t, 0, cur + (t - ptr + 1) * (new_xr - 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++) {
      sum[i][j] = a[i][j];
      if (j > 0) {
        sum[i][j] += sum[i][j - 1];
      }
    }
  }
  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;
}

Compilation message

soccer.cpp: In function 'void rec(int, int, int, int, int, int)':
soccer.cpp:75:11: warning: unused variable 'new_xl' [-Wunused-variable]
   75 |       int new_xl = xl;
      |           ^~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20828 KB ok
2 Correct 2 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20924 KB ok
5 Correct 2 ms 16732 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 5 ms 43612 KB ok
8 Correct 34 ms 95168 KB ok
9 Correct 494 ms 519504 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20828 KB ok
2 Correct 2 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20924 KB ok
6 Correct 2 ms 20824 KB ok
7 Correct 2 ms 20824 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 21080 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20824 KB ok
13 Correct 2 ms 20824 KB ok
14 Correct 2 ms 20828 KB ok
15 Correct 2 ms 20932 KB ok
16 Correct 2 ms 20828 KB ok
17 Correct 2 ms 20824 KB ok
18 Correct 2 ms 20828 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 2 ms 20824 KB ok
21 Correct 2 ms 20828 KB ok
22 Correct 2 ms 20828 KB ok
23 Correct 2 ms 20828 KB ok
24 Correct 2 ms 20828 KB ok
25 Correct 2 ms 20828 KB ok
26 Correct 2 ms 20828 KB ok
27 Correct 2 ms 20828 KB ok
28 Correct 2 ms 20824 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 4 ms 31068 KB ok
31 Correct 4 ms 31068 KB ok
32 Correct 3 ms 31068 KB ok
33 Correct 3 ms 31068 KB ok
34 Correct 3 ms 31228 KB ok
35 Correct 3 ms 31064 KB ok
36 Correct 3 ms 31064 KB ok
37 Correct 3 ms 31068 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 4 ms 31200 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 31068 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20828 KB ok
2 Correct 2 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20924 KB ok
6 Correct 2 ms 20824 KB ok
7 Correct 2 ms 20824 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 21080 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20824 KB ok
13 Correct 2 ms 20824 KB ok
14 Correct 2 ms 20828 KB ok
15 Correct 2 ms 20932 KB ok
16 Correct 2 ms 20828 KB ok
17 Correct 2 ms 20824 KB ok
18 Correct 2 ms 20828 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 2 ms 20824 KB ok
21 Correct 2 ms 20828 KB ok
22 Correct 2 ms 20828 KB ok
23 Correct 2 ms 20828 KB ok
24 Correct 2 ms 20828 KB ok
25 Correct 2 ms 20828 KB ok
26 Correct 2 ms 20828 KB ok
27 Correct 2 ms 20828 KB ok
28 Correct 2 ms 20824 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 4 ms 31068 KB ok
31 Correct 4 ms 31068 KB ok
32 Correct 3 ms 31068 KB ok
33 Correct 3 ms 31068 KB ok
34 Correct 3 ms 31228 KB ok
35 Correct 3 ms 31064 KB ok
36 Correct 3 ms 31064 KB ok
37 Correct 3 ms 31068 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 4 ms 31200 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 31068 KB ok
42 Correct 163 ms 117452 KB ok
43 Correct 144 ms 115140 KB ok
44 Correct 190 ms 114692 KB ok
45 Correct 163 ms 114280 KB ok
46 Correct 181 ms 116172 KB ok
47 Correct 34 ms 102720 KB ok
48 Correct 197 ms 106344 KB ok
49 Correct 226 ms 105372 KB ok
50 Correct 84 ms 111044 KB ok
51 Correct 69 ms 111052 KB ok
52 Correct 115 ms 102056 KB ok
53 Correct 33 ms 99416 KB ok
54 Correct 156 ms 100948 KB ok
55 Correct 331 ms 104200 KB ok
56 Correct 36 ms 100956 KB ok
57 Correct 86 ms 114072 KB ok
58 Correct 98 ms 115188 KB ok
59 Correct 107 ms 116536 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20828 KB ok
2 Correct 2 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20924 KB ok
6 Correct 2 ms 16732 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 5 ms 43612 KB ok
9 Correct 34 ms 95168 KB ok
10 Correct 494 ms 519504 KB ok
11 Correct 2 ms 20824 KB ok
12 Correct 2 ms 20824 KB ok
13 Correct 2 ms 20828 KB ok
14 Correct 2 ms 20828 KB ok
15 Correct 2 ms 21080 KB ok
16 Correct 2 ms 20828 KB ok
17 Correct 2 ms 20824 KB ok
18 Correct 2 ms 20824 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 2 ms 20932 KB ok
21 Correct 2 ms 20828 KB ok
22 Correct 2 ms 20824 KB ok
23 Correct 2 ms 20828 KB ok
24 Correct 2 ms 20828 KB ok
25 Correct 2 ms 20824 KB ok
26 Correct 2 ms 20828 KB ok
27 Correct 2 ms 20828 KB ok
28 Correct 2 ms 20828 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 2 ms 20828 KB ok
31 Correct 2 ms 20828 KB ok
32 Correct 2 ms 20828 KB ok
33 Correct 2 ms 20824 KB ok
34 Correct 2 ms 20828 KB ok
35 Correct 4 ms 31068 KB ok
36 Correct 4 ms 31068 KB ok
37 Correct 3 ms 31068 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 31228 KB ok
40 Correct 3 ms 31064 KB ok
41 Correct 3 ms 31064 KB ok
42 Correct 3 ms 31068 KB ok
43 Correct 3 ms 31068 KB ok
44 Correct 4 ms 31200 KB ok
45 Correct 3 ms 31068 KB ok
46 Correct 3 ms 31068 KB ok
47 Correct 163 ms 117452 KB ok
48 Correct 144 ms 115140 KB ok
49 Correct 190 ms 114692 KB ok
50 Correct 163 ms 114280 KB ok
51 Correct 181 ms 116172 KB ok
52 Correct 34 ms 102720 KB ok
53 Correct 197 ms 106344 KB ok
54 Correct 226 ms 105372 KB ok
55 Correct 84 ms 111044 KB ok
56 Correct 69 ms 111052 KB ok
57 Correct 115 ms 102056 KB ok
58 Correct 33 ms 99416 KB ok
59 Correct 156 ms 100948 KB ok
60 Correct 331 ms 104200 KB ok
61 Correct 36 ms 100956 KB ok
62 Correct 86 ms 114072 KB ok
63 Correct 98 ms 115188 KB ok
64 Correct 107 ms 116536 KB ok
65 Execution timed out 4575 ms 739800 KB Time limit exceeded
66 Halted 0 ms 0 KB -