oj.uz

Submission #1017082

# Submission time Handle Problem Language Result Execution time Memory
1017082 2024-07-08T20:28:01 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 625580 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 == 0 || get_sum(xl - 1, ptr, t) > 0) ? xl : query_U(xl - 1, ptr, t));
      rec(new_xl, new_xr, ptr, t, 0, 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, -1, 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 2 ms 20828 KB ok
3 Correct 2 ms 20828 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 43612 KB ok
8 Correct 33 ms 99408 KB ok
9 Correct 492 ms 519248 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 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 20828 KB ok
9 Correct 2 ms 20824 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 2 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20824 KB ok
6 Correct 2 ms 20824 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 20824 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 20828 KB ok
16 Correct 2 ms 20828 KB ok
17 Correct 2 ms 20828 KB ok
18 Correct 2 ms 20920 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 2 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20824 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20824 KB ok
8 Correct 2 ms 20824 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 20824 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 20828 KB ok
18 Correct 2 ms 20828 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 2 ms 20920 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 20824 KB ok
30 Correct 4 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 31068 KB ok
35 Correct 3 ms 31068 KB ok
36 Correct 3 ms 31452 KB ok
37 Correct 3 ms 31068 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 31176 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 20824 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20824 KB ok
8 Correct 2 ms 20824 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 20824 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 20828 KB ok
18 Correct 2 ms 20828 KB ok
19 Correct 2 ms 20828 KB ok
20 Correct 2 ms 20920 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 20824 KB ok
30 Correct 4 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 31068 KB ok
35 Correct 3 ms 31068 KB ok
36 Correct 3 ms 31452 KB ok
37 Correct 3 ms 31068 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 31176 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 31068 KB ok
42 Correct 119 ms 110280 KB ok
43 Correct 119 ms 110644 KB ok
44 Correct 85 ms 104088 KB ok
45 Correct 74 ms 104784 KB ok
46 Correct 108 ms 108236 KB ok
47 Correct 33 ms 102340 KB ok
48 Correct 42 ms 102444 KB ok
49 Correct 37 ms 101716 KB ok
50 Correct 63 ms 107200 KB ok
51 Correct 46 ms 104392 KB ok
52 Correct 73 ms 99916 KB ok
53 Correct 32 ms 99248 KB ok
54 Correct 74 ms 101524 KB ok
55 Correct 115 ms 102484 KB ok
56 Correct 31 ms 101464 KB ok
57 Correct 75 ms 110416 KB ok
58 Correct 80 ms 111440 KB ok
59 Correct 95 ms 114004 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 20824 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 33 ms 99408 KB ok
10 Correct 492 ms 519248 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 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 20920 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 20824 KB ok
35 Correct 4 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 31068 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 31452 KB ok
42 Correct 3 ms 31068 KB ok
43 Correct 3 ms 31068 KB ok
44 Correct 3 ms 31176 KB ok
45 Correct 3 ms 31068 KB ok
46 Correct 3 ms 31068 KB ok
47 Correct 119 ms 110280 KB ok
48 Correct 119 ms 110644 KB ok
49 Correct 85 ms 104088 KB ok
50 Correct 74 ms 104784 KB ok
51 Correct 108 ms 108236 KB ok
52 Correct 33 ms 102340 KB ok
53 Correct 42 ms 102444 KB ok
54 Correct 37 ms 101716 KB ok
55 Correct 63 ms 107200 KB ok
56 Correct 46 ms 104392 KB ok
57 Correct 73 ms 99916 KB ok
58 Correct 32 ms 99248 KB ok
59 Correct 74 ms 101524 KB ok
60 Correct 115 ms 102484 KB ok
61 Correct 31 ms 101464 KB ok
62 Correct 75 ms 110416 KB ok
63 Correct 80 ms 111440 KB ok
64 Correct 95 ms 114004 KB ok
65 Correct 3032 ms 625580 KB ok
66 Correct 1287 ms 616288 KB ok
67 Correct 730 ms 558828 KB ok
68 Correct 1181 ms 532048 KB ok
69 Correct 1816 ms 555852 KB ok
70 Correct 2158 ms 575696 KB ok
71 Correct 954 ms 529756 KB ok
72 Correct 508 ms 526928 KB ok
73 Correct 717 ms 523796 KB ok
74 Correct 725 ms 523788 KB ok
75 Correct 725 ms 524184 KB ok
76 Correct 1095 ms 605336 KB ok
77 Correct 1108 ms 605276 KB ok
78 Correct 1373 ms 546328 KB ok
79 Correct 641 ms 536580 KB ok
80 Correct 591 ms 534472 KB ok
81 Correct 607 ms 534724 KB ok
82 Correct 1006 ms 542240 KB ok
83 Correct 978 ms 567536 KB ok
84 Correct 2510 ms 493396 KB ok
85 Correct 599 ms 484948 KB ok
86 Correct 2763 ms 497532 KB ok
87 Execution timed out 4557 ms 495400 KB Time limit exceeded
88 Halted 0 ms 0 KB -