oj.uz

Submission #1017132

# Submission time Handle Problem Language Result Execution time Memory
1017132 2024-07-08T22:08:51 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 735896 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[LOG][MAX][MAX];
int st_D[LOG][MAX][MAX];
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[k][i][l], st_U[k][i][r - (1 << k) + 1]);
}
 
int query_D(int i, int l, int r) {
  int k = logs[r - l + 1];
  return min(st_D[k][i][l], st_D[k][i][r - (1 << k) + 1]);
}
 
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[0][i][j] = U[i][j];
      st_D[0][i][j] = 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[k][i][j] = max(st_U[k - 1][i][j], st_U[k - 1][i][j + (1 << (k - 1))]);
        st_D[k][i][j] = min(st_D[k - 1][i][j], st_D[k - 1][i][j + (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 74 ms 189328 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 189264 KB ok
2 Correct 71 ms 189264 KB ok
3 Correct 73 ms 189680 KB ok
4 Correct 67 ms 189772 KB ok
5 Correct 65 ms 189268 KB ok
6 Correct 67 ms 189260 KB ok
7 Correct 68 ms 198508 KB ok
8 Correct 107 ms 263760 KB ok
9 Correct 500 ms 675920 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 189264 KB ok
2 Correct 71 ms 189264 KB ok
3 Correct 66 ms 189268 KB ok
4 Correct 67 ms 189268 KB ok
5 Correct 67 ms 189268 KB ok
6 Correct 64 ms 189216 KB ok
7 Correct 66 ms 189268 KB ok
8 Correct 64 ms 189264 KB ok
9 Correct 72 ms 189268 KB ok
10 Correct 68 ms 189264 KB ok
11 Correct 69 ms 189264 KB ok
12 Correct 68 ms 189264 KB ok
13 Correct 66 ms 189264 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 189328 KB ok
2 Correct 68 ms 189264 KB ok
3 Correct 71 ms 189264 KB ok
4 Correct 66 ms 189268 KB ok
5 Correct 67 ms 189268 KB ok
6 Correct 67 ms 189268 KB ok
7 Correct 64 ms 189216 KB ok
8 Correct 66 ms 189268 KB ok
9 Correct 64 ms 189264 KB ok
10 Correct 72 ms 189268 KB ok
11 Correct 68 ms 189264 KB ok
12 Correct 69 ms 189264 KB ok
13 Correct 68 ms 189264 KB ok
14 Correct 66 ms 189264 KB ok
15 Correct 67 ms 189520 KB ok
16 Correct 66 ms 189504 KB ok
17 Correct 65 ms 189436 KB ok
18 Correct 64 ms 189492 KB ok
19 Correct 66 ms 189520 KB ok
20 Correct 65 ms 189524 KB ok
21 Correct 64 ms 189524 KB ok
22 Correct 70 ms 189516 KB ok
23 Correct 81 ms 189396 KB ok
24 Correct 64 ms 189520 KB ok
25 Correct 67 ms 189520 KB ok
26 Correct 69 ms 189404 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 189328 KB ok
2 Correct 68 ms 189264 KB ok
3 Correct 71 ms 189264 KB ok
4 Correct 73 ms 189680 KB ok
5 Correct 67 ms 189772 KB ok
6 Correct 66 ms 189268 KB ok
7 Correct 67 ms 189268 KB ok
8 Correct 67 ms 189268 KB ok
9 Correct 64 ms 189216 KB ok
10 Correct 66 ms 189268 KB ok
11 Correct 64 ms 189264 KB ok
12 Correct 72 ms 189268 KB ok
13 Correct 68 ms 189264 KB ok
14 Correct 69 ms 189264 KB ok
15 Correct 68 ms 189264 KB ok
16 Correct 66 ms 189264 KB ok
17 Correct 67 ms 189520 KB ok
18 Correct 66 ms 189504 KB ok
19 Correct 65 ms 189436 KB ok
20 Correct 64 ms 189492 KB ok
21 Correct 66 ms 189520 KB ok
22 Correct 65 ms 189524 KB ok
23 Correct 64 ms 189524 KB ok
24 Correct 70 ms 189516 KB ok
25 Correct 81 ms 189396 KB ok
26 Correct 64 ms 189520 KB ok
27 Correct 67 ms 189520 KB ok
28 Correct 69 ms 189404 KB ok
29 Correct 67 ms 189524 KB ok
30 Correct 73 ms 191200 KB ok
31 Correct 71 ms 191244 KB ok
32 Correct 65 ms 191308 KB ok
33 Correct 66 ms 191568 KB ok
34 Correct 69 ms 191276 KB ok
35 Correct 70 ms 191056 KB ok
36 Correct 67 ms 191060 KB ok
37 Correct 83 ms 191112 KB ok
38 Correct 65 ms 191116 KB ok
39 Correct 73 ms 191064 KB ok
40 Correct 73 ms 191204 KB ok
41 Correct 67 ms 191340 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 189328 KB ok
2 Correct 68 ms 189264 KB ok
3 Correct 71 ms 189264 KB ok
4 Correct 73 ms 189680 KB ok
5 Correct 67 ms 189772 KB ok
6 Correct 66 ms 189268 KB ok
7 Correct 67 ms 189268 KB ok
8 Correct 67 ms 189268 KB ok
9 Correct 64 ms 189216 KB ok
10 Correct 66 ms 189268 KB ok
11 Correct 64 ms 189264 KB ok
12 Correct 72 ms 189268 KB ok
13 Correct 68 ms 189264 KB ok
14 Correct 69 ms 189264 KB ok
15 Correct 68 ms 189264 KB ok
16 Correct 66 ms 189264 KB ok
17 Correct 67 ms 189520 KB ok
18 Correct 66 ms 189504 KB ok
19 Correct 65 ms 189436 KB ok
20 Correct 64 ms 189492 KB ok
21 Correct 66 ms 189520 KB ok
22 Correct 65 ms 189524 KB ok
23 Correct 64 ms 189524 KB ok
24 Correct 70 ms 189516 KB ok
25 Correct 81 ms 189396 KB ok
26 Correct 64 ms 189520 KB ok
27 Correct 67 ms 189520 KB ok
28 Correct 69 ms 189404 KB ok
29 Correct 67 ms 189524 KB ok
30 Correct 73 ms 191200 KB ok
31 Correct 71 ms 191244 KB ok
32 Correct 65 ms 191308 KB ok
33 Correct 66 ms 191568 KB ok
34 Correct 69 ms 191276 KB ok
35 Correct 70 ms 191056 KB ok
36 Correct 67 ms 191060 KB ok
37 Correct 83 ms 191112 KB ok
38 Correct 65 ms 191116 KB ok
39 Correct 73 ms 191064 KB ok
40 Correct 73 ms 191204 KB ok
41 Correct 67 ms 191340 KB ok
42 Correct 143 ms 267240 KB ok
43 Correct 142 ms 268428 KB ok
44 Correct 122 ms 264784 KB ok
45 Correct 123 ms 264272 KB ok
46 Correct 136 ms 266192 KB ok
47 Correct 108 ms 263764 KB ok
48 Correct 118 ms 261716 KB ok
49 Correct 113 ms 261712 KB ok
50 Correct 117 ms 264892 KB ok
51 Correct 113 ms 265080 KB ok
52 Correct 114 ms 257104 KB ok
53 Correct 115 ms 254552 KB ok
54 Correct 142 ms 257180 KB ok
55 Correct 126 ms 259924 KB ok
56 Correct 102 ms 257360 KB ok
57 Correct 127 ms 267860 KB ok
58 Correct 123 ms 268372 KB ok
59 Correct 125 ms 268952 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 189328 KB ok
2 Correct 68 ms 189264 KB ok
3 Correct 71 ms 189264 KB ok
4 Correct 73 ms 189680 KB ok
5 Correct 67 ms 189772 KB ok
6 Correct 65 ms 189268 KB ok
7 Correct 67 ms 189260 KB ok
8 Correct 68 ms 198508 KB ok
9 Correct 107 ms 263760 KB ok
10 Correct 500 ms 675920 KB ok
11 Correct 66 ms 189268 KB ok
12 Correct 67 ms 189268 KB ok
13 Correct 67 ms 189268 KB ok
14 Correct 64 ms 189216 KB ok
15 Correct 66 ms 189268 KB ok
16 Correct 64 ms 189264 KB ok
17 Correct 72 ms 189268 KB ok
18 Correct 68 ms 189264 KB ok
19 Correct 69 ms 189264 KB ok
20 Correct 68 ms 189264 KB ok
21 Correct 66 ms 189264 KB ok
22 Correct 67 ms 189520 KB ok
23 Correct 66 ms 189504 KB ok
24 Correct 65 ms 189436 KB ok
25 Correct 64 ms 189492 KB ok
26 Correct 66 ms 189520 KB ok
27 Correct 65 ms 189524 KB ok
28 Correct 64 ms 189524 KB ok
29 Correct 70 ms 189516 KB ok
30 Correct 81 ms 189396 KB ok
31 Correct 64 ms 189520 KB ok
32 Correct 67 ms 189520 KB ok
33 Correct 69 ms 189404 KB ok
34 Correct 67 ms 189524 KB ok
35 Correct 73 ms 191200 KB ok
36 Correct 71 ms 191244 KB ok
37 Correct 65 ms 191308 KB ok
38 Correct 66 ms 191568 KB ok
39 Correct 69 ms 191276 KB ok
40 Correct 70 ms 191056 KB ok
41 Correct 67 ms 191060 KB ok
42 Correct 83 ms 191112 KB ok
43 Correct 65 ms 191116 KB ok
44 Correct 73 ms 191064 KB ok
45 Correct 73 ms 191204 KB ok
46 Correct 67 ms 191340 KB ok
47 Correct 143 ms 267240 KB ok
48 Correct 142 ms 268428 KB ok
49 Correct 122 ms 264784 KB ok
50 Correct 123 ms 264272 KB ok
51 Correct 136 ms 266192 KB ok
52 Correct 108 ms 263764 KB ok
53 Correct 118 ms 261716 KB ok
54 Correct 113 ms 261712 KB ok
55 Correct 117 ms 264892 KB ok
56 Correct 113 ms 265080 KB ok
57 Correct 114 ms 257104 KB ok
58 Correct 115 ms 254552 KB ok
59 Correct 142 ms 257180 KB ok
60 Correct 126 ms 259924 KB ok
61 Correct 102 ms 257360 KB ok
62 Correct 127 ms 267860 KB ok
63 Correct 123 ms 268372 KB ok
64 Correct 125 ms 268952 KB ok
65 Correct 1296 ms 732160 KB ok
66 Correct 864 ms 735896 KB ok
67 Correct 609 ms 702300 KB ok
68 Correct 747 ms 678308 KB ok
69 Correct 1008 ms 690372 KB ok
70 Correct 1095 ms 701128 KB ok
71 Correct 634 ms 677204 KB ok
72 Correct 486 ms 675844 KB ok
73 Correct 713 ms 668508 KB ok
74 Correct 623 ms 668436 KB ok
75 Correct 629 ms 669392 KB ok
76 Correct 758 ms 692240 KB ok
77 Correct 687 ms 692236 KB ok
78 Correct 968 ms 688396 KB ok
79 Correct 529 ms 681136 KB ok
80 Correct 545 ms 679536 KB ok
81 Correct 530 ms 679452 KB ok
82 Correct 679 ms 683544 KB ok
83 Correct 750 ms 698792 KB ok
84 Correct 1137 ms 630100 KB ok
85 Correct 476 ms 623456 KB ok
86 Correct 1192 ms 634364 KB ok
87 Execution timed out 4554 ms 637264 KB Time limit exceeded
88 Halted 0 ms 0 KB -