oj.uz

Submission #1017138

# Submission time Handle Problem Language Result Execution time Memory
1017138 2024-07-08T22:18:18 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
28 / 100
 4500 ms 730864 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});
      rec(new_xl, new_xr, ptr, t, cur + (t - ptr + 1) * (xl - new_xl + new_xr - xr));
      ptr = R[xr + 1][ptr] + 1;
    }
  }
  /* 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) {
        if (i > 0 && get_sum(i - 1, j, R[i][j]) == 0) {
          continue;
        }
        if (i + 1 < n && get_sum(i + 1, j, R[i][j]) == 0 && ((j > 0 && a[i + 1][j - 1] == 0) || (R[i][j] + 1 < n && a[j + 1][R[i][j] + 1] == 0))) {
          continue;
        }
        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 69 ms 189324 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 69 ms 189264 KB ok
3 Correct 67 ms 189776 KB ok
4 Correct 66 ms 189780 KB ok
5 Correct 75 ms 189184 KB ok
6 Correct 67 ms 189264 KB ok
7 Correct 69 ms 198424 KB ok
8 Correct 103 ms 263760 KB ok
9 Correct 494 ms 675628 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 69 ms 189264 KB ok
3 Correct 71 ms 189268 KB ok
4 Correct 70 ms 189200 KB ok
5 Correct 73 ms 189304 KB ok
6 Correct 66 ms 189268 KB ok
7 Correct 66 ms 189228 KB ok
8 Correct 73 ms 189264 KB ok
9 Correct 67 ms 189216 KB ok
10 Correct 69 ms 189264 KB ok
11 Correct 68 ms 189176 KB ok
12 Correct 65 ms 189300 KB ok
13 Correct 67 ms 189268 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 189324 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 69 ms 189264 KB ok
4 Correct 71 ms 189268 KB ok
5 Correct 70 ms 189200 KB ok
6 Correct 73 ms 189304 KB ok
7 Correct 66 ms 189268 KB ok
8 Correct 66 ms 189228 KB ok
9 Correct 73 ms 189264 KB ok
10 Correct 67 ms 189216 KB ok
11 Correct 69 ms 189264 KB ok
12 Correct 68 ms 189176 KB ok
13 Correct 65 ms 189300 KB ok
14 Correct 67 ms 189268 KB ok
15 Correct 66 ms 189604 KB ok
16 Correct 68 ms 189524 KB ok
17 Partially correct 68 ms 189520 KB partial
18 Correct 68 ms 189520 KB ok
19 Correct 69 ms 189524 KB ok
20 Correct 70 ms 189376 KB ok
21 Correct 67 ms 189464 KB ok
22 Correct 67 ms 189520 KB ok
23 Correct 67 ms 189580 KB ok
24 Correct 68 ms 189524 KB ok
25 Correct 70 ms 189524 KB ok
26 Correct 66 ms 189484 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 189324 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 69 ms 189264 KB ok
4 Correct 67 ms 189776 KB ok
5 Correct 66 ms 189780 KB ok
6 Correct 71 ms 189268 KB ok
7 Correct 70 ms 189200 KB ok
8 Correct 73 ms 189304 KB ok
9 Correct 66 ms 189268 KB ok
10 Correct 66 ms 189228 KB ok
11 Correct 73 ms 189264 KB ok
12 Correct 67 ms 189216 KB ok
13 Correct 69 ms 189264 KB ok
14 Correct 68 ms 189176 KB ok
15 Correct 65 ms 189300 KB ok
16 Correct 67 ms 189268 KB ok
17 Correct 66 ms 189604 KB ok
18 Correct 68 ms 189524 KB ok
19 Partially correct 68 ms 189520 KB partial
20 Correct 68 ms 189520 KB ok
21 Correct 69 ms 189524 KB ok
22 Correct 70 ms 189376 KB ok
23 Correct 67 ms 189464 KB ok
24 Correct 67 ms 189520 KB ok
25 Correct 67 ms 189580 KB ok
26 Correct 68 ms 189524 KB ok
27 Correct 70 ms 189524 KB ok
28 Correct 66 ms 189484 KB ok
29 Correct 67 ms 189524 KB ok
30 Correct 67 ms 191312 KB ok
31 Correct 66 ms 191440 KB ok
32 Correct 69 ms 191312 KB ok
33 Correct 66 ms 191312 KB ok
34 Correct 69 ms 191316 KB ok
35 Correct 87 ms 191060 KB ok
36 Correct 68 ms 191056 KB ok
37 Correct 67 ms 191056 KB ok
38 Correct 71 ms 191056 KB ok
39 Correct 68 ms 191060 KB ok
40 Correct 66 ms 191056 KB ok
41 Correct 67 ms 191320 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 189324 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 69 ms 189264 KB ok
4 Correct 67 ms 189776 KB ok
5 Correct 66 ms 189780 KB ok
6 Correct 71 ms 189268 KB ok
7 Correct 70 ms 189200 KB ok
8 Correct 73 ms 189304 KB ok
9 Correct 66 ms 189268 KB ok
10 Correct 66 ms 189228 KB ok
11 Correct 73 ms 189264 KB ok
12 Correct 67 ms 189216 KB ok
13 Correct 69 ms 189264 KB ok
14 Correct 68 ms 189176 KB ok
15 Correct 65 ms 189300 KB ok
16 Correct 67 ms 189268 KB ok
17 Correct 66 ms 189604 KB ok
18 Correct 68 ms 189524 KB ok
19 Partially correct 68 ms 189520 KB partial
20 Correct 68 ms 189520 KB ok
21 Correct 69 ms 189524 KB ok
22 Correct 70 ms 189376 KB ok
23 Correct 67 ms 189464 KB ok
24 Correct 67 ms 189520 KB ok
25 Correct 67 ms 189580 KB ok
26 Correct 68 ms 189524 KB ok
27 Correct 70 ms 189524 KB ok
28 Correct 66 ms 189484 KB ok
29 Correct 67 ms 189524 KB ok
30 Correct 67 ms 191312 KB ok
31 Correct 66 ms 191440 KB ok
32 Correct 69 ms 191312 KB ok
33 Correct 66 ms 191312 KB ok
34 Correct 69 ms 191316 KB ok
35 Correct 87 ms 191060 KB ok
36 Correct 68 ms 191056 KB ok
37 Correct 67 ms 191056 KB ok
38 Correct 71 ms 191056 KB ok
39 Correct 68 ms 191060 KB ok
40 Correct 66 ms 191056 KB ok
41 Correct 67 ms 191320 KB ok
42 Correct 126 ms 267068 KB ok
43 Correct 139 ms 267980 KB ok
44 Correct 115 ms 264780 KB ok
45 Correct 113 ms 264272 KB ok
46 Correct 125 ms 266068 KB ok
47 Correct 101 ms 263764 KB ok
48 Correct 111 ms 261924 KB ok
49 Correct 106 ms 261696 KB ok
50 Correct 109 ms 263764 KB ok
51 Correct 110 ms 264908 KB ok
52 Correct 121 ms 257064 KB ok
53 Correct 101 ms 254284 KB ok
54 Correct 106 ms 257204 KB ok
55 Correct 118 ms 260052 KB ok
56 Correct 102 ms 257364 KB ok
57 Correct 114 ms 267800 KB ok
58 Correct 124 ms 268364 KB ok
59 Correct 123 ms 268884 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 189324 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 69 ms 189264 KB ok
4 Correct 67 ms 189776 KB ok
5 Correct 66 ms 189780 KB ok
6 Correct 75 ms 189184 KB ok
7 Correct 67 ms 189264 KB ok
8 Correct 69 ms 198424 KB ok
9 Correct 103 ms 263760 KB ok
10 Correct 494 ms 675628 KB ok
11 Correct 71 ms 189268 KB ok
12 Correct 70 ms 189200 KB ok
13 Correct 73 ms 189304 KB ok
14 Correct 66 ms 189268 KB ok
15 Correct 66 ms 189228 KB ok
16 Correct 73 ms 189264 KB ok
17 Correct 67 ms 189216 KB ok
18 Correct 69 ms 189264 KB ok
19 Correct 68 ms 189176 KB ok
20 Correct 65 ms 189300 KB ok
21 Correct 67 ms 189268 KB ok
22 Correct 66 ms 189604 KB ok
23 Correct 68 ms 189524 KB ok
24 Partially correct 68 ms 189520 KB partial
25 Correct 68 ms 189520 KB ok
26 Correct 69 ms 189524 KB ok
27 Correct 70 ms 189376 KB ok
28 Correct 67 ms 189464 KB ok
29 Correct 67 ms 189520 KB ok
30 Correct 67 ms 189580 KB ok
31 Correct 68 ms 189524 KB ok
32 Correct 70 ms 189524 KB ok
33 Correct 66 ms 189484 KB ok
34 Correct 67 ms 189524 KB ok
35 Correct 67 ms 191312 KB ok
36 Correct 66 ms 191440 KB ok
37 Correct 69 ms 191312 KB ok
38 Correct 66 ms 191312 KB ok
39 Correct 69 ms 191316 KB ok
40 Correct 87 ms 191060 KB ok
41 Correct 68 ms 191056 KB ok
42 Correct 67 ms 191056 KB ok
43 Correct 71 ms 191056 KB ok
44 Correct 68 ms 191060 KB ok
45 Correct 66 ms 191056 KB ok
46 Correct 67 ms 191320 KB ok
47 Correct 126 ms 267068 KB ok
48 Correct 139 ms 267980 KB ok
49 Correct 115 ms 264780 KB ok
50 Correct 113 ms 264272 KB ok
51 Correct 125 ms 266068 KB ok
52 Correct 101 ms 263764 KB ok
53 Correct 111 ms 261924 KB ok
54 Correct 106 ms 261696 KB ok
55 Correct 109 ms 263764 KB ok
56 Correct 110 ms 264908 KB ok
57 Correct 121 ms 257064 KB ok
58 Correct 101 ms 254284 KB ok
59 Correct 106 ms 257204 KB ok
60 Correct 118 ms 260052 KB ok
61 Correct 102 ms 257364 KB ok
62 Correct 114 ms 267800 KB ok
63 Correct 124 ms 268364 KB ok
64 Correct 123 ms 268884 KB ok
65 Correct 1068 ms 728560 KB ok
66 Correct 884 ms 730864 KB ok
67 Correct 622 ms 701644 KB ok
68 Correct 615 ms 678224 KB ok
69 Correct 786 ms 690016 KB ok
70 Correct 903 ms 700032 KB ok
71 Correct 608 ms 677060 KB ok
72 Correct 503 ms 675736 KB ok
73 Correct 564 ms 668248 KB ok
74 Correct 540 ms 668500 KB ok
75 Correct 592 ms 668584 KB ok
76 Correct 530 ms 675808 KB ok
77 Correct 521 ms 675924 KB ok
78 Correct 736 ms 687140 KB ok
79 Correct 522 ms 680648 KB ok
80 Correct 531 ms 678856 KB ok
81 Correct 518 ms 678948 KB ok
82 Correct 601 ms 682704 KB ok
83 Correct 663 ms 696224 KB ok
84 Correct 798 ms 629672 KB ok
85 Correct 482 ms 623424 KB ok
86 Correct 770 ms 634196 KB ok
87 Execution timed out 4568 ms 637300 KB Time limit exceeded
88 Halted 0 ms 0 KB -