oj.uz

Submission #1017135

# Submission time Handle Problem Language Result Execution time Memory
1017135 2024-07-08T22:14:26 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});
      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) {
        int from = query_U(i, j, R[i][j]);
        int to = query_D(i, j, R[i][j]);
        s.push_back({(to - from + 1) * (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 66 ms 189528 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 189244 KB ok
2 Correct 77 ms 189268 KB ok
3 Correct 66 ms 189780 KB ok
4 Correct 81 ms 189704 KB ok
5 Correct 66 ms 189268 KB ok
6 Correct 65 ms 189268 KB ok
7 Correct 96 ms 198420 KB ok
8 Correct 105 ms 263764 KB ok
9 Correct 576 ms 675924 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 189244 KB ok
2 Correct 77 ms 189268 KB ok
3 Correct 72 ms 189348 KB ok
4 Correct 67 ms 189268 KB ok
5 Correct 71 ms 189264 KB ok
6 Correct 69 ms 189328 KB ok
7 Correct 66 ms 189268 KB ok
8 Correct 67 ms 189312 KB ok
9 Correct 72 ms 189268 KB ok
10 Correct 67 ms 189264 KB ok
11 Correct 70 ms 189268 KB ok
12 Correct 68 ms 189264 KB ok
13 Correct 73 ms 189196 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189528 KB ok
2 Correct 71 ms 189244 KB ok
3 Correct 77 ms 189268 KB ok
4 Correct 72 ms 189348 KB ok
5 Correct 67 ms 189268 KB ok
6 Correct 71 ms 189264 KB ok
7 Correct 69 ms 189328 KB ok
8 Correct 66 ms 189268 KB ok
9 Correct 67 ms 189312 KB ok
10 Correct 72 ms 189268 KB ok
11 Correct 67 ms 189264 KB ok
12 Correct 70 ms 189268 KB ok
13 Correct 68 ms 189264 KB ok
14 Correct 73 ms 189196 KB ok
15 Correct 72 ms 189628 KB ok
16 Correct 74 ms 189520 KB ok
17 Correct 66 ms 189620 KB ok
18 Correct 71 ms 189524 KB ok
19 Correct 71 ms 189520 KB ok
20 Correct 69 ms 189524 KB ok
21 Correct 68 ms 189428 KB ok
22 Correct 83 ms 189512 KB ok
23 Correct 68 ms 189468 KB ok
24 Correct 69 ms 189600 KB ok
25 Correct 69 ms 189560 KB ok
26 Correct 68 ms 189480 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189528 KB ok
2 Correct 71 ms 189244 KB ok
3 Correct 77 ms 189268 KB ok
4 Correct 66 ms 189780 KB ok
5 Correct 81 ms 189704 KB ok
6 Correct 72 ms 189348 KB ok
7 Correct 67 ms 189268 KB ok
8 Correct 71 ms 189264 KB ok
9 Correct 69 ms 189328 KB ok
10 Correct 66 ms 189268 KB ok
11 Correct 67 ms 189312 KB ok
12 Correct 72 ms 189268 KB ok
13 Correct 67 ms 189264 KB ok
14 Correct 70 ms 189268 KB ok
15 Correct 68 ms 189264 KB ok
16 Correct 73 ms 189196 KB ok
17 Correct 72 ms 189628 KB ok
18 Correct 74 ms 189520 KB ok
19 Correct 66 ms 189620 KB ok
20 Correct 71 ms 189524 KB ok
21 Correct 71 ms 189520 KB ok
22 Correct 69 ms 189524 KB ok
23 Correct 68 ms 189428 KB ok
24 Correct 83 ms 189512 KB ok
25 Correct 68 ms 189468 KB ok
26 Correct 69 ms 189600 KB ok
27 Correct 69 ms 189560 KB ok
28 Correct 68 ms 189480 KB ok
29 Correct 69 ms 189604 KB ok
30 Correct 73 ms 191228 KB ok
31 Correct 71 ms 191372 KB ok
32 Correct 71 ms 191312 KB ok
33 Correct 85 ms 191312 KB ok
34 Correct 69 ms 191316 KB ok
35 Correct 71 ms 191056 KB ok
36 Correct 68 ms 191056 KB ok
37 Correct 71 ms 191060 KB ok
38 Correct 73 ms 191012 KB ok
39 Correct 69 ms 191056 KB ok
40 Correct 72 ms 191060 KB ok
41 Correct 70 ms 191312 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189528 KB ok
2 Correct 71 ms 189244 KB ok
3 Correct 77 ms 189268 KB ok
4 Correct 66 ms 189780 KB ok
5 Correct 81 ms 189704 KB ok
6 Correct 72 ms 189348 KB ok
7 Correct 67 ms 189268 KB ok
8 Correct 71 ms 189264 KB ok
9 Correct 69 ms 189328 KB ok
10 Correct 66 ms 189268 KB ok
11 Correct 67 ms 189312 KB ok
12 Correct 72 ms 189268 KB ok
13 Correct 67 ms 189264 KB ok
14 Correct 70 ms 189268 KB ok
15 Correct 68 ms 189264 KB ok
16 Correct 73 ms 189196 KB ok
17 Correct 72 ms 189628 KB ok
18 Correct 74 ms 189520 KB ok
19 Correct 66 ms 189620 KB ok
20 Correct 71 ms 189524 KB ok
21 Correct 71 ms 189520 KB ok
22 Correct 69 ms 189524 KB ok
23 Correct 68 ms 189428 KB ok
24 Correct 83 ms 189512 KB ok
25 Correct 68 ms 189468 KB ok
26 Correct 69 ms 189600 KB ok
27 Correct 69 ms 189560 KB ok
28 Correct 68 ms 189480 KB ok
29 Correct 69 ms 189604 KB ok
30 Correct 73 ms 191228 KB ok
31 Correct 71 ms 191372 KB ok
32 Correct 71 ms 191312 KB ok
33 Correct 85 ms 191312 KB ok
34 Correct 69 ms 191316 KB ok
35 Correct 71 ms 191056 KB ok
36 Correct 68 ms 191056 KB ok
37 Correct 71 ms 191060 KB ok
38 Correct 73 ms 191012 KB ok
39 Correct 69 ms 191056 KB ok
40 Correct 72 ms 191060 KB ok
41 Correct 70 ms 191312 KB ok
42 Correct 155 ms 267468 KB ok
43 Correct 145 ms 268284 KB ok
44 Correct 123 ms 264628 KB ok
45 Correct 119 ms 264432 KB ok
46 Correct 133 ms 266192 KB ok
47 Correct 107 ms 263696 KB ok
48 Correct 191 ms 261716 KB ok
49 Correct 179 ms 261836 KB ok
50 Correct 123 ms 264904 KB ok
51 Correct 125 ms 264944 KB ok
52 Correct 207 ms 256908 KB ok
53 Correct 113 ms 254292 KB ok
54 Correct 202 ms 257252 KB ok
55 Correct 317 ms 260188 KB ok
56 Correct 112 ms 257364 KB ok
57 Correct 897 ms 267936 KB ok
58 Correct 847 ms 268556 KB ok
59 Correct 770 ms 268880 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189528 KB ok
2 Correct 71 ms 189244 KB ok
3 Correct 77 ms 189268 KB ok
4 Correct 66 ms 189780 KB ok
5 Correct 81 ms 189704 KB ok
6 Correct 66 ms 189268 KB ok
7 Correct 65 ms 189268 KB ok
8 Correct 96 ms 198420 KB ok
9 Correct 105 ms 263764 KB ok
10 Correct 576 ms 675924 KB ok
11 Correct 72 ms 189348 KB ok
12 Correct 67 ms 189268 KB ok
13 Correct 71 ms 189264 KB ok
14 Correct 69 ms 189328 KB ok
15 Correct 66 ms 189268 KB ok
16 Correct 67 ms 189312 KB ok
17 Correct 72 ms 189268 KB ok
18 Correct 67 ms 189264 KB ok
19 Correct 70 ms 189268 KB ok
20 Correct 68 ms 189264 KB ok
21 Correct 73 ms 189196 KB ok
22 Correct 72 ms 189628 KB ok
23 Correct 74 ms 189520 KB ok
24 Correct 66 ms 189620 KB ok
25 Correct 71 ms 189524 KB ok
26 Correct 71 ms 189520 KB ok
27 Correct 69 ms 189524 KB ok
28 Correct 68 ms 189428 KB ok
29 Correct 83 ms 189512 KB ok
30 Correct 68 ms 189468 KB ok
31 Correct 69 ms 189600 KB ok
32 Correct 69 ms 189560 KB ok
33 Correct 68 ms 189480 KB ok
34 Correct 69 ms 189604 KB ok
35 Correct 73 ms 191228 KB ok
36 Correct 71 ms 191372 KB ok
37 Correct 71 ms 191312 KB ok
38 Correct 85 ms 191312 KB ok
39 Correct 69 ms 191316 KB ok
40 Correct 71 ms 191056 KB ok
41 Correct 68 ms 191056 KB ok
42 Correct 71 ms 191060 KB ok
43 Correct 73 ms 191012 KB ok
44 Correct 69 ms 191056 KB ok
45 Correct 72 ms 191060 KB ok
46 Correct 70 ms 191312 KB ok
47 Correct 155 ms 267468 KB ok
48 Correct 145 ms 268284 KB ok
49 Correct 123 ms 264628 KB ok
50 Correct 119 ms 264432 KB ok
51 Correct 133 ms 266192 KB ok
52 Correct 107 ms 263696 KB ok
53 Correct 191 ms 261716 KB ok
54 Correct 179 ms 261836 KB ok
55 Correct 123 ms 264904 KB ok
56 Correct 125 ms 264944 KB ok
57 Correct 207 ms 256908 KB ok
58 Correct 113 ms 254292 KB ok
59 Correct 202 ms 257252 KB ok
60 Correct 317 ms 260188 KB ok
61 Correct 112 ms 257364 KB ok
62 Correct 897 ms 267936 KB ok
63 Correct 847 ms 268556 KB ok
64 Correct 770 ms 268880 KB ok
65 Correct 1286 ms 732028 KB ok
66 Correct 943 ms 735896 KB ok
67 Correct 629 ms 702200 KB ok
68 Correct 615 ms 678224 KB ok
69 Correct 846 ms 690372 KB ok
70 Correct 1028 ms 700864 KB ok
71 Correct 548 ms 677132 KB ok
72 Correct 496 ms 675920 KB ok
73 Execution timed out 4561 ms 668344 KB Time limit exceeded
74 Halted 0 ms 0 KB -