oj.uz

Submission #1017129

# Submission time Handle Problem Language Result Execution time Memory
1017129 2024-07-08T22:05:01 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 767380 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<pair<int, int>, int> mp[MAX][MAX];
 
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 cur) {
  if (mp[xl][yr][{yl, yr}] >= cur) {
    return;
  }
  res = max(res, cur);
  mp[xl][yr][{yl, yr}] = cur;
  vector<array<int, 5>> to;
  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));
      to.push_back({cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr), new_xl, new_xr, ptr, t});
      //rec(new_xl, new_xr, ptr, t, 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 == 0 || get_sum(xl - 1, ptr, t) > 0) ? xl : query_U(xl - 1, ptr, t));
      to.push_back({cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr), new_xl, new_xr, ptr, t});
      ptr = R[xr + 1][ptr] + 1;
    }
  }
  sort(to.begin(), to.end(), [&](array<int, 5> a, array<int, 5> b) {
    int val_a = ((a[3] == yl || a[4] == yr) ? 0 : 1);
    int val_b = ((b[3] == yl || b[4] == yr) ? 0 : 1);
    return val_a > val_b;
  });
  for (int i = 0; i < (int) to.size(); i++) {
    rec(to[i][1], to[i][2], to[i][3], to[i][4], to[i][0]);
  }
}
 
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];
    int from = query_U(i, l, r);
    int to = query_D(i, l, r);
    rec(from, to, l, r, (to - from + 1) * (r - l + 1));
  }
  return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 189264 KB ok
2 Correct 72 ms 189268 KB ok
3 Correct 64 ms 189372 KB ok
4 Correct 67 ms 189520 KB ok
5 Correct 64 ms 189084 KB ok
6 Correct 65 ms 189268 KB ok
7 Correct 71 ms 194112 KB ok
8 Correct 99 ms 239632 KB ok
9 Correct 568 ms 707232 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 189264 KB ok
2 Correct 72 ms 189268 KB ok
3 Correct 79 ms 189220 KB ok
4 Correct 64 ms 189268 KB ok
5 Correct 67 ms 189268 KB ok
6 Correct 73 ms 189260 KB ok
7 Correct 64 ms 189372 KB ok
8 Correct 64 ms 189268 KB ok
9 Correct 64 ms 189268 KB ok
10 Correct 66 ms 189264 KB ok
11 Correct 74 ms 189216 KB ok
12 Correct 63 ms 189228 KB ok
13 Correct 76 ms 189268 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 189268 KB ok
2 Correct 64 ms 189264 KB ok
3 Correct 72 ms 189268 KB ok
4 Correct 79 ms 189220 KB ok
5 Correct 64 ms 189268 KB ok
6 Correct 67 ms 189268 KB ok
7 Correct 73 ms 189260 KB ok
8 Correct 64 ms 189372 KB ok
9 Correct 64 ms 189268 KB ok
10 Correct 64 ms 189268 KB ok
11 Correct 66 ms 189264 KB ok
12 Correct 74 ms 189216 KB ok
13 Correct 63 ms 189228 KB ok
14 Correct 76 ms 189268 KB ok
15 Correct 62 ms 189520 KB ok
16 Correct 64 ms 189396 KB ok
17 Correct 65 ms 189268 KB ok
18 Correct 69 ms 189276 KB ok
19 Correct 79 ms 189264 KB ok
20 Correct 64 ms 189268 KB ok
21 Correct 68 ms 189520 KB ok
22 Correct 64 ms 189268 KB ok
23 Correct 65 ms 189464 KB ok
24 Correct 65 ms 189312 KB ok
25 Correct 67 ms 189264 KB ok
26 Correct 65 ms 189520 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 189268 KB ok
2 Correct 64 ms 189264 KB ok
3 Correct 72 ms 189268 KB ok
4 Correct 64 ms 189372 KB ok
5 Correct 67 ms 189520 KB ok
6 Correct 79 ms 189220 KB ok
7 Correct 64 ms 189268 KB ok
8 Correct 67 ms 189268 KB ok
9 Correct 73 ms 189260 KB ok
10 Correct 64 ms 189372 KB ok
11 Correct 64 ms 189268 KB ok
12 Correct 64 ms 189268 KB ok
13 Correct 66 ms 189264 KB ok
14 Correct 74 ms 189216 KB ok
15 Correct 63 ms 189228 KB ok
16 Correct 76 ms 189268 KB ok
17 Correct 62 ms 189520 KB ok
18 Correct 64 ms 189396 KB ok
19 Correct 65 ms 189268 KB ok
20 Correct 69 ms 189276 KB ok
21 Correct 79 ms 189264 KB ok
22 Correct 64 ms 189268 KB ok
23 Correct 68 ms 189520 KB ok
24 Correct 64 ms 189268 KB ok
25 Correct 65 ms 189464 KB ok
26 Correct 65 ms 189312 KB ok
27 Correct 67 ms 189264 KB ok
28 Correct 65 ms 189520 KB ok
29 Correct 65 ms 189268 KB ok
30 Correct 65 ms 190288 KB ok
31 Correct 65 ms 190292 KB ok
32 Correct 64 ms 190288 KB ok
33 Correct 70 ms 190224 KB ok
34 Correct 66 ms 190292 KB ok
35 Correct 66 ms 190036 KB ok
36 Correct 65 ms 190020 KB ok
37 Correct 65 ms 190032 KB ok
38 Correct 66 ms 190024 KB ok
39 Correct 65 ms 190296 KB ok
40 Correct 65 ms 190204 KB ok
41 Correct 69 ms 190292 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 189268 KB ok
2 Correct 64 ms 189264 KB ok
3 Correct 72 ms 189268 KB ok
4 Correct 64 ms 189372 KB ok
5 Correct 67 ms 189520 KB ok
6 Correct 79 ms 189220 KB ok
7 Correct 64 ms 189268 KB ok
8 Correct 67 ms 189268 KB ok
9 Correct 73 ms 189260 KB ok
10 Correct 64 ms 189372 KB ok
11 Correct 64 ms 189268 KB ok
12 Correct 64 ms 189268 KB ok
13 Correct 66 ms 189264 KB ok
14 Correct 74 ms 189216 KB ok
15 Correct 63 ms 189228 KB ok
16 Correct 76 ms 189268 KB ok
17 Correct 62 ms 189520 KB ok
18 Correct 64 ms 189396 KB ok
19 Correct 65 ms 189268 KB ok
20 Correct 69 ms 189276 KB ok
21 Correct 79 ms 189264 KB ok
22 Correct 64 ms 189268 KB ok
23 Correct 68 ms 189520 KB ok
24 Correct 64 ms 189268 KB ok
25 Correct 65 ms 189464 KB ok
26 Correct 65 ms 189312 KB ok
27 Correct 67 ms 189264 KB ok
28 Correct 65 ms 189520 KB ok
29 Correct 65 ms 189268 KB ok
30 Correct 65 ms 190288 KB ok
31 Correct 65 ms 190292 KB ok
32 Correct 64 ms 190288 KB ok
33 Correct 70 ms 190224 KB ok
34 Correct 66 ms 190292 KB ok
35 Correct 66 ms 190036 KB ok
36 Correct 65 ms 190020 KB ok
37 Correct 65 ms 190032 KB ok
38 Correct 66 ms 190024 KB ok
39 Correct 65 ms 190296 KB ok
40 Correct 65 ms 190204 KB ok
41 Correct 69 ms 190292 KB ok
42 Correct 154 ms 243356 KB ok
43 Correct 136 ms 244156 KB ok
44 Correct 140 ms 240456 KB ok
45 Correct 115 ms 240208 KB ok
46 Correct 125 ms 241872 KB ok
47 Correct 104 ms 239644 KB ok
48 Correct 108 ms 237632 KB ok
49 Correct 105 ms 237392 KB ok
50 Correct 122 ms 240780 KB ok
51 Correct 109 ms 240796 KB ok
52 Correct 110 ms 232788 KB ok
53 Correct 98 ms 230160 KB ok
54 Correct 122 ms 233044 KB ok
55 Correct 121 ms 235832 KB ok
56 Correct 97 ms 233296 KB ok
57 Correct 117 ms 243792 KB ok
58 Correct 123 ms 244200 KB ok
59 Correct 119 ms 244820 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 189268 KB ok
2 Correct 64 ms 189264 KB ok
3 Correct 72 ms 189268 KB ok
4 Correct 64 ms 189372 KB ok
5 Correct 67 ms 189520 KB ok
6 Correct 64 ms 189084 KB ok
7 Correct 65 ms 189268 KB ok
8 Correct 71 ms 194112 KB ok
9 Correct 99 ms 239632 KB ok
10 Correct 568 ms 707232 KB ok
11 Correct 79 ms 189220 KB ok
12 Correct 64 ms 189268 KB ok
13 Correct 67 ms 189268 KB ok
14 Correct 73 ms 189260 KB ok
15 Correct 64 ms 189372 KB ok
16 Correct 64 ms 189268 KB ok
17 Correct 64 ms 189268 KB ok
18 Correct 66 ms 189264 KB ok
19 Correct 74 ms 189216 KB ok
20 Correct 63 ms 189228 KB ok
21 Correct 76 ms 189268 KB ok
22 Correct 62 ms 189520 KB ok
23 Correct 64 ms 189396 KB ok
24 Correct 65 ms 189268 KB ok
25 Correct 69 ms 189276 KB ok
26 Correct 79 ms 189264 KB ok
27 Correct 64 ms 189268 KB ok
28 Correct 68 ms 189520 KB ok
29 Correct 64 ms 189268 KB ok
30 Correct 65 ms 189464 KB ok
31 Correct 65 ms 189312 KB ok
32 Correct 67 ms 189264 KB ok
33 Correct 65 ms 189520 KB ok
34 Correct 65 ms 189268 KB ok
35 Correct 65 ms 190288 KB ok
36 Correct 65 ms 190292 KB ok
37 Correct 64 ms 190288 KB ok
38 Correct 70 ms 190224 KB ok
39 Correct 66 ms 190292 KB ok
40 Correct 66 ms 190036 KB ok
41 Correct 65 ms 190020 KB ok
42 Correct 65 ms 190032 KB ok
43 Correct 66 ms 190024 KB ok
44 Correct 65 ms 190296 KB ok
45 Correct 65 ms 190204 KB ok
46 Correct 69 ms 190292 KB ok
47 Correct 154 ms 243356 KB ok
48 Correct 136 ms 244156 KB ok
49 Correct 140 ms 240456 KB ok
50 Correct 115 ms 240208 KB ok
51 Correct 125 ms 241872 KB ok
52 Correct 104 ms 239644 KB ok
53 Correct 108 ms 237632 KB ok
54 Correct 105 ms 237392 KB ok
55 Correct 122 ms 240780 KB ok
56 Correct 109 ms 240796 KB ok
57 Correct 110 ms 232788 KB ok
58 Correct 98 ms 230160 KB ok
59 Correct 122 ms 233044 KB ok
60 Correct 121 ms 235832 KB ok
61 Correct 97 ms 233296 KB ok
62 Correct 117 ms 243792 KB ok
63 Correct 123 ms 244200 KB ok
64 Correct 119 ms 244820 KB ok
65 Correct 1470 ms 763640 KB ok
66 Correct 1043 ms 767380 KB ok
67 Correct 728 ms 733696 KB ok
68 Correct 846 ms 709808 KB ok
69 Correct 1054 ms 721888 KB ok
70 Correct 1163 ms 732404 KB ok
71 Correct 722 ms 708520 KB ok
72 Correct 606 ms 707288 KB ok
73 Correct 792 ms 699652 KB ok
74 Correct 747 ms 700024 KB ok
75 Correct 799 ms 700068 KB ok
76 Correct 858 ms 723744 KB ok
77 Correct 849 ms 723724 KB ok
78 Correct 1076 ms 720088 KB ok
79 Correct 635 ms 712472 KB ok
80 Correct 648 ms 710960 KB ok
81 Correct 630 ms 710956 KB ok
82 Correct 758 ms 714756 KB ok
83 Correct 824 ms 730280 KB ok
84 Correct 1285 ms 661332 KB ok
85 Correct 594 ms 654672 KB ok
86 Correct 1328 ms 666220 KB ok
87 Execution timed out 4551 ms 668752 KB Time limit exceeded
88 Halted 0 ms 0 KB -