oj.uz

Submission #1017133

# Submission time Handle Problem Language Result Execution time Memory
1017133 2024-07-08T22:10:32 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 736148 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) {
        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 67 ms 189376 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189352 KB ok
2 Correct 69 ms 189268 KB ok
3 Correct 66 ms 189584 KB ok
4 Correct 65 ms 189780 KB ok
5 Correct 74 ms 189232 KB ok
6 Correct 66 ms 189264 KB ok
7 Correct 71 ms 198484 KB ok
8 Correct 101 ms 263896 KB ok
9 Correct 474 ms 675752 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189352 KB ok
2 Correct 69 ms 189268 KB ok
3 Correct 68 ms 189160 KB ok
4 Correct 69 ms 189268 KB ok
5 Correct 68 ms 189264 KB ok
6 Correct 65 ms 189264 KB ok
7 Correct 66 ms 189260 KB ok
8 Correct 68 ms 189264 KB ok
9 Correct 67 ms 189152 KB ok
10 Correct 67 ms 189324 KB ok
11 Correct 65 ms 189264 KB ok
12 Correct 68 ms 189268 KB ok
13 Correct 66 ms 189268 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189376 KB ok
2 Correct 66 ms 189352 KB ok
3 Correct 69 ms 189268 KB ok
4 Correct 68 ms 189160 KB ok
5 Correct 69 ms 189268 KB ok
6 Correct 68 ms 189264 KB ok
7 Correct 65 ms 189264 KB ok
8 Correct 66 ms 189260 KB ok
9 Correct 68 ms 189264 KB ok
10 Correct 67 ms 189152 KB ok
11 Correct 67 ms 189324 KB ok
12 Correct 65 ms 189264 KB ok
13 Correct 68 ms 189268 KB ok
14 Correct 66 ms 189268 KB ok
15 Correct 72 ms 189440 KB ok
16 Correct 65 ms 189508 KB ok
17 Correct 65 ms 189532 KB ok
18 Correct 67 ms 189524 KB ok
19 Correct 67 ms 189568 KB ok
20 Correct 71 ms 189520 KB ok
21 Correct 67 ms 189436 KB ok
22 Correct 66 ms 189524 KB ok
23 Correct 70 ms 189524 KB ok
24 Correct 66 ms 189372 KB ok
25 Correct 69 ms 189388 KB ok
26 Correct 68 ms 189520 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189376 KB ok
2 Correct 66 ms 189352 KB ok
3 Correct 69 ms 189268 KB ok
4 Correct 66 ms 189584 KB ok
5 Correct 65 ms 189780 KB ok
6 Correct 68 ms 189160 KB ok
7 Correct 69 ms 189268 KB ok
8 Correct 68 ms 189264 KB ok
9 Correct 65 ms 189264 KB ok
10 Correct 66 ms 189260 KB ok
11 Correct 68 ms 189264 KB ok
12 Correct 67 ms 189152 KB ok
13 Correct 67 ms 189324 KB ok
14 Correct 65 ms 189264 KB ok
15 Correct 68 ms 189268 KB ok
16 Correct 66 ms 189268 KB ok
17 Correct 72 ms 189440 KB ok
18 Correct 65 ms 189508 KB ok
19 Correct 65 ms 189532 KB ok
20 Correct 67 ms 189524 KB ok
21 Correct 67 ms 189568 KB ok
22 Correct 71 ms 189520 KB ok
23 Correct 67 ms 189436 KB ok
24 Correct 66 ms 189524 KB ok
25 Correct 70 ms 189524 KB ok
26 Correct 66 ms 189372 KB ok
27 Correct 69 ms 189388 KB ok
28 Correct 68 ms 189520 KB ok
29 Correct 65 ms 189536 KB ok
30 Correct 70 ms 191316 KB ok
31 Correct 67 ms 191212 KB ok
32 Correct 66 ms 191312 KB ok
33 Correct 67 ms 191312 KB ok
34 Correct 66 ms 191316 KB ok
35 Correct 67 ms 191076 KB ok
36 Correct 67 ms 191080 KB ok
37 Correct 71 ms 191056 KB ok
38 Correct 67 ms 191060 KB ok
39 Correct 72 ms 191112 KB ok
40 Correct 68 ms 191060 KB ok
41 Correct 66 ms 191204 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189376 KB ok
2 Correct 66 ms 189352 KB ok
3 Correct 69 ms 189268 KB ok
4 Correct 66 ms 189584 KB ok
5 Correct 65 ms 189780 KB ok
6 Correct 68 ms 189160 KB ok
7 Correct 69 ms 189268 KB ok
8 Correct 68 ms 189264 KB ok
9 Correct 65 ms 189264 KB ok
10 Correct 66 ms 189260 KB ok
11 Correct 68 ms 189264 KB ok
12 Correct 67 ms 189152 KB ok
13 Correct 67 ms 189324 KB ok
14 Correct 65 ms 189264 KB ok
15 Correct 68 ms 189268 KB ok
16 Correct 66 ms 189268 KB ok
17 Correct 72 ms 189440 KB ok
18 Correct 65 ms 189508 KB ok
19 Correct 65 ms 189532 KB ok
20 Correct 67 ms 189524 KB ok
21 Correct 67 ms 189568 KB ok
22 Correct 71 ms 189520 KB ok
23 Correct 67 ms 189436 KB ok
24 Correct 66 ms 189524 KB ok
25 Correct 70 ms 189524 KB ok
26 Correct 66 ms 189372 KB ok
27 Correct 69 ms 189388 KB ok
28 Correct 68 ms 189520 KB ok
29 Correct 65 ms 189536 KB ok
30 Correct 70 ms 191316 KB ok
31 Correct 67 ms 191212 KB ok
32 Correct 66 ms 191312 KB ok
33 Correct 67 ms 191312 KB ok
34 Correct 66 ms 191316 KB ok
35 Correct 67 ms 191076 KB ok
36 Correct 67 ms 191080 KB ok
37 Correct 71 ms 191056 KB ok
38 Correct 67 ms 191060 KB ok
39 Correct 72 ms 191112 KB ok
40 Correct 68 ms 191060 KB ok
41 Correct 66 ms 191204 KB ok
42 Correct 131 ms 267208 KB ok
43 Correct 133 ms 268228 KB ok
44 Correct 116 ms 264788 KB ok
45 Correct 121 ms 264272 KB ok
46 Correct 123 ms 266184 KB ok
47 Correct 107 ms 263904 KB ok
48 Correct 106 ms 261712 KB ok
49 Correct 105 ms 261712 KB ok
50 Correct 112 ms 264908 KB ok
51 Correct 129 ms 265064 KB ok
52 Correct 107 ms 256852 KB ok
53 Correct 103 ms 254292 KB ok
54 Correct 124 ms 257108 KB ok
55 Correct 115 ms 260108 KB ok
56 Correct 103 ms 257364 KB ok
57 Correct 114 ms 267856 KB ok
58 Correct 120 ms 268368 KB ok
59 Correct 118 ms 268896 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189376 KB ok
2 Correct 66 ms 189352 KB ok
3 Correct 69 ms 189268 KB ok
4 Correct 66 ms 189584 KB ok
5 Correct 65 ms 189780 KB ok
6 Correct 74 ms 189232 KB ok
7 Correct 66 ms 189264 KB ok
8 Correct 71 ms 198484 KB ok
9 Correct 101 ms 263896 KB ok
10 Correct 474 ms 675752 KB ok
11 Correct 68 ms 189160 KB ok
12 Correct 69 ms 189268 KB ok
13 Correct 68 ms 189264 KB ok
14 Correct 65 ms 189264 KB ok
15 Correct 66 ms 189260 KB ok
16 Correct 68 ms 189264 KB ok
17 Correct 67 ms 189152 KB ok
18 Correct 67 ms 189324 KB ok
19 Correct 65 ms 189264 KB ok
20 Correct 68 ms 189268 KB ok
21 Correct 66 ms 189268 KB ok
22 Correct 72 ms 189440 KB ok
23 Correct 65 ms 189508 KB ok
24 Correct 65 ms 189532 KB ok
25 Correct 67 ms 189524 KB ok
26 Correct 67 ms 189568 KB ok
27 Correct 71 ms 189520 KB ok
28 Correct 67 ms 189436 KB ok
29 Correct 66 ms 189524 KB ok
30 Correct 70 ms 189524 KB ok
31 Correct 66 ms 189372 KB ok
32 Correct 69 ms 189388 KB ok
33 Correct 68 ms 189520 KB ok
34 Correct 65 ms 189536 KB ok
35 Correct 70 ms 191316 KB ok
36 Correct 67 ms 191212 KB ok
37 Correct 66 ms 191312 KB ok
38 Correct 67 ms 191312 KB ok
39 Correct 66 ms 191316 KB ok
40 Correct 67 ms 191076 KB ok
41 Correct 67 ms 191080 KB ok
42 Correct 71 ms 191056 KB ok
43 Correct 67 ms 191060 KB ok
44 Correct 72 ms 191112 KB ok
45 Correct 68 ms 191060 KB ok
46 Correct 66 ms 191204 KB ok
47 Correct 131 ms 267208 KB ok
48 Correct 133 ms 268228 KB ok
49 Correct 116 ms 264788 KB ok
50 Correct 121 ms 264272 KB ok
51 Correct 123 ms 266184 KB ok
52 Correct 107 ms 263904 KB ok
53 Correct 106 ms 261712 KB ok
54 Correct 105 ms 261712 KB ok
55 Correct 112 ms 264908 KB ok
56 Correct 129 ms 265064 KB ok
57 Correct 107 ms 256852 KB ok
58 Correct 103 ms 254292 KB ok
59 Correct 124 ms 257108 KB ok
60 Correct 115 ms 260108 KB ok
61 Correct 103 ms 257364 KB ok
62 Correct 114 ms 267856 KB ok
63 Correct 120 ms 268368 KB ok
64 Correct 118 ms 268896 KB ok
65 Correct 1140 ms 732120 KB ok
66 Correct 848 ms 736148 KB ok
67 Correct 638 ms 702376 KB ok
68 Correct 641 ms 678232 KB ok
69 Correct 888 ms 690500 KB ok
70 Correct 897 ms 700936 KB ok
71 Correct 635 ms 677152 KB ok
72 Correct 502 ms 675924 KB ok
73 Correct 550 ms 668240 KB ok
74 Correct 596 ms 668348 KB ok
75 Correct 559 ms 668760 KB ok
76 Correct 666 ms 692268 KB ok
77 Correct 748 ms 692408 KB ok
78 Correct 776 ms 688400 KB ok
79 Correct 547 ms 681408 KB ok
80 Correct 542 ms 679556 KB ok
81 Correct 515 ms 679568 KB ok
82 Correct 656 ms 683488 KB ok
83 Correct 743 ms 698920 KB ok
84 Correct 766 ms 629660 KB ok
85 Correct 485 ms 623092 KB ok
86 Correct 822 ms 634300 KB ok
87 Execution timed out 4562 ms 637244 KB Time limit exceeded
88 Halted 0 ms 0 KB -