oj.uz

Submission #1017086

# Submission time Handle Problem Language Result Execution time Memory
1017086 2024-07-08T20:30:42 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 600184 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, 4>, 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 cur) {
  if (mp[{xl, xr, yl, yr}] >= cur) {
    return;
  }
  res = max(res, cur);
  mp[{xl, xr, yl, yr}] = 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, 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));
      rec(new_xl, new_xr, ptr, t, cur + (t - ptr + 1) * (xl - new_xl + 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, r - l + 1);
  }
  return res;
}

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 3 ms 20828 KB ok
3 Correct 2 ms 20824 KB ok
4 Correct 2 ms 20824 KB ok
5 Correct 2 ms 16732 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 5 ms 43608 KB ok
8 Correct 32 ms 100952 KB ok
9 Correct 532 ms 519216 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20828 KB ok
2 Correct 3 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20824 KB ok
6 Correct 2 ms 20920 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 2 ms 20924 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 20828 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20828 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 3 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20828 KB ok
6 Correct 2 ms 20824 KB ok
7 Correct 2 ms 20920 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20924 KB ok
10 Correct 2 ms 20828 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20828 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 20828 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 20828 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 3 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 20824 KB ok
9 Correct 2 ms 20920 KB ok
10 Correct 2 ms 20828 KB ok
11 Correct 2 ms 20924 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20828 KB ok
14 Correct 2 ms 20828 KB ok
15 Correct 2 ms 20828 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 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 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 3 ms 31068 KB ok
31 Correct 3 ms 31068 KB ok
32 Correct 3 ms 31068 KB ok
33 Correct 3 ms 31068 KB ok
34 Correct 3 ms 31064 KB ok
35 Correct 3 ms 31064 KB ok
36 Correct 3 ms 31068 KB ok
37 Correct 3 ms 31064 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 31068 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 3 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 20824 KB ok
9 Correct 2 ms 20920 KB ok
10 Correct 2 ms 20828 KB ok
11 Correct 2 ms 20924 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20828 KB ok
14 Correct 2 ms 20828 KB ok
15 Correct 2 ms 20828 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 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 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 3 ms 31068 KB ok
31 Correct 3 ms 31068 KB ok
32 Correct 3 ms 31068 KB ok
33 Correct 3 ms 31068 KB ok
34 Correct 3 ms 31064 KB ok
35 Correct 3 ms 31064 KB ok
36 Correct 3 ms 31068 KB ok
37 Correct 3 ms 31064 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 31068 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 31068 KB ok
42 Correct 91 ms 100976 KB ok
43 Correct 96 ms 101024 KB ok
44 Correct 63 ms 101944 KB ok
45 Correct 56 ms 101336 KB ok
46 Correct 81 ms 103736 KB ok
47 Correct 32 ms 100944 KB ok
48 Correct 36 ms 99408 KB ok
49 Correct 35 ms 100184 KB ok
50 Correct 61 ms 104132 KB ok
51 Correct 46 ms 101388 KB ok
52 Correct 50 ms 98644 KB ok
53 Correct 31 ms 96336 KB ok
54 Correct 52 ms 97104 KB ok
55 Correct 71 ms 101020 KB ok
56 Correct 31 ms 96928 KB ok
57 Correct 48 ms 103504 KB ok
58 Correct 57 ms 105556 KB ok
59 Correct 65 ms 106064 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 3 ms 20828 KB ok
4 Correct 2 ms 20824 KB ok
5 Correct 2 ms 20824 KB ok
6 Correct 2 ms 16732 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 5 ms 43608 KB ok
9 Correct 32 ms 100952 KB ok
10 Correct 532 ms 519216 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20824 KB ok
14 Correct 2 ms 20920 KB ok
15 Correct 2 ms 20828 KB ok
16 Correct 2 ms 20924 KB ok
17 Correct 2 ms 20828 KB ok
18 Correct 2 ms 20828 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 20824 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 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 20828 KB ok
34 Correct 2 ms 20828 KB ok
35 Correct 3 ms 31068 KB ok
36 Correct 3 ms 31068 KB ok
37 Correct 3 ms 31068 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 31064 KB ok
40 Correct 3 ms 31064 KB ok
41 Correct 3 ms 31068 KB ok
42 Correct 3 ms 31064 KB ok
43 Correct 3 ms 31068 KB ok
44 Correct 3 ms 31068 KB ok
45 Correct 3 ms 31068 KB ok
46 Correct 3 ms 31068 KB ok
47 Correct 91 ms 100976 KB ok
48 Correct 96 ms 101024 KB ok
49 Correct 63 ms 101944 KB ok
50 Correct 56 ms 101336 KB ok
51 Correct 81 ms 103736 KB ok
52 Correct 32 ms 100944 KB ok
53 Correct 36 ms 99408 KB ok
54 Correct 35 ms 100184 KB ok
55 Correct 61 ms 104132 KB ok
56 Correct 46 ms 101388 KB ok
57 Correct 50 ms 98644 KB ok
58 Correct 31 ms 96336 KB ok
59 Correct 52 ms 97104 KB ok
60 Correct 71 ms 101020 KB ok
61 Correct 31 ms 96928 KB ok
62 Correct 48 ms 103504 KB ok
63 Correct 57 ms 105556 KB ok
64 Correct 65 ms 106064 KB ok
65 Correct 2224 ms 590108 KB ok
66 Correct 1096 ms 600184 KB ok
67 Correct 656 ms 549292 KB ok
68 Correct 878 ms 521812 KB ok
69 Correct 1271 ms 535488 KB ok
70 Correct 1472 ms 547840 KB ok
71 Correct 729 ms 520788 KB ok
72 Correct 496 ms 519200 KB ok
73 Correct 649 ms 515920 KB ok
74 Correct 649 ms 515924 KB ok
75 Correct 642 ms 516144 KB ok
76 Correct 1138 ms 597400 KB ok
77 Correct 1053 ms 597360 KB ok
78 Correct 1117 ms 538212 KB ok
79 Correct 567 ms 527680 KB ok
80 Correct 569 ms 525768 KB ok
81 Correct 584 ms 525252 KB ok
82 Correct 803 ms 529608 KB ok
83 Correct 894 ms 553640 KB ok
84 Correct 1583 ms 485460 KB ok
85 Correct 515 ms 477212 KB ok
86 Correct 1665 ms 489828 KB ok
87 Execution timed out 4562 ms 495696 KB Time limit exceeded
88 Halted 0 ms 0 KB -