oj.uz

Submission #1017141

# Submission time Handle Problem Language Result Execution time Memory
1017141 2024-07-08T22:28:14 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
100 / 100
 4258 ms 767284 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][xr][{yl, yr}] >= cur) {
    return;
  }
  res = max(res, cur);
  mp[xl][xr][{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);
      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);
      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[i + 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 71 ms 189384 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 68 ms 189272 KB ok
3 Correct 67 ms 189780 KB ok
4 Correct 65 ms 189780 KB ok
5 Correct 68 ms 189268 KB ok
6 Correct 64 ms 189264 KB ok
7 Correct 69 ms 198480 KB ok
8 Correct 103 ms 263676 KB ok
9 Correct 490 ms 675668 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 68 ms 189272 KB ok
3 Correct 69 ms 189264 KB ok
4 Correct 74 ms 189200 KB ok
5 Correct 65 ms 189268 KB ok
6 Correct 65 ms 189268 KB ok
7 Correct 68 ms 189264 KB ok
8 Correct 76 ms 189268 KB ok
9 Correct 76 ms 189224 KB ok
10 Correct 67 ms 189248 KB ok
11 Correct 68 ms 189352 KB ok
12 Correct 67 ms 189380 KB ok
13 Correct 68 ms 189336 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 189384 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 68 ms 189272 KB ok
4 Correct 69 ms 189264 KB ok
5 Correct 74 ms 189200 KB ok
6 Correct 65 ms 189268 KB ok
7 Correct 65 ms 189268 KB ok
8 Correct 68 ms 189264 KB ok
9 Correct 76 ms 189268 KB ok
10 Correct 76 ms 189224 KB ok
11 Correct 67 ms 189248 KB ok
12 Correct 68 ms 189352 KB ok
13 Correct 67 ms 189380 KB ok
14 Correct 68 ms 189336 KB ok
15 Correct 68 ms 189524 KB ok
16 Correct 66 ms 189524 KB ok
17 Correct 83 ms 189516 KB ok
18 Correct 65 ms 189528 KB ok
19 Correct 66 ms 189524 KB ok
20 Correct 70 ms 189592 KB ok
21 Correct 66 ms 189496 KB ok
22 Correct 71 ms 189420 KB ok
23 Correct 68 ms 189448 KB ok
24 Correct 65 ms 189584 KB ok
25 Correct 66 ms 189592 KB ok
26 Correct 66 ms 189520 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 189384 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 68 ms 189272 KB ok
4 Correct 67 ms 189780 KB ok
5 Correct 65 ms 189780 KB ok
6 Correct 69 ms 189264 KB ok
7 Correct 74 ms 189200 KB ok
8 Correct 65 ms 189268 KB ok
9 Correct 65 ms 189268 KB ok
10 Correct 68 ms 189264 KB ok
11 Correct 76 ms 189268 KB ok
12 Correct 76 ms 189224 KB ok
13 Correct 67 ms 189248 KB ok
14 Correct 68 ms 189352 KB ok
15 Correct 67 ms 189380 KB ok
16 Correct 68 ms 189336 KB ok
17 Correct 68 ms 189524 KB ok
18 Correct 66 ms 189524 KB ok
19 Correct 83 ms 189516 KB ok
20 Correct 65 ms 189528 KB ok
21 Correct 66 ms 189524 KB ok
22 Correct 70 ms 189592 KB ok
23 Correct 66 ms 189496 KB ok
24 Correct 71 ms 189420 KB ok
25 Correct 68 ms 189448 KB ok
26 Correct 65 ms 189584 KB ok
27 Correct 66 ms 189592 KB ok
28 Correct 66 ms 189520 KB ok
29 Correct 65 ms 189524 KB ok
30 Correct 65 ms 191312 KB ok
31 Correct 75 ms 191312 KB ok
32 Correct 65 ms 191316 KB ok
33 Correct 69 ms 191316 KB ok
34 Correct 67 ms 191284 KB ok
35 Correct 66 ms 190988 KB ok
36 Correct 67 ms 191104 KB ok
37 Correct 68 ms 191056 KB ok
38 Correct 67 ms 191016 KB ok
39 Correct 67 ms 191120 KB ok
40 Correct 66 ms 191056 KB ok
41 Correct 71 ms 191312 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 189384 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 68 ms 189272 KB ok
4 Correct 67 ms 189780 KB ok
5 Correct 65 ms 189780 KB ok
6 Correct 69 ms 189264 KB ok
7 Correct 74 ms 189200 KB ok
8 Correct 65 ms 189268 KB ok
9 Correct 65 ms 189268 KB ok
10 Correct 68 ms 189264 KB ok
11 Correct 76 ms 189268 KB ok
12 Correct 76 ms 189224 KB ok
13 Correct 67 ms 189248 KB ok
14 Correct 68 ms 189352 KB ok
15 Correct 67 ms 189380 KB ok
16 Correct 68 ms 189336 KB ok
17 Correct 68 ms 189524 KB ok
18 Correct 66 ms 189524 KB ok
19 Correct 83 ms 189516 KB ok
20 Correct 65 ms 189528 KB ok
21 Correct 66 ms 189524 KB ok
22 Correct 70 ms 189592 KB ok
23 Correct 66 ms 189496 KB ok
24 Correct 71 ms 189420 KB ok
25 Correct 68 ms 189448 KB ok
26 Correct 65 ms 189584 KB ok
27 Correct 66 ms 189592 KB ok
28 Correct 66 ms 189520 KB ok
29 Correct 65 ms 189524 KB ok
30 Correct 65 ms 191312 KB ok
31 Correct 75 ms 191312 KB ok
32 Correct 65 ms 191316 KB ok
33 Correct 69 ms 191316 KB ok
34 Correct 67 ms 191284 KB ok
35 Correct 66 ms 190988 KB ok
36 Correct 67 ms 191104 KB ok
37 Correct 68 ms 191056 KB ok
38 Correct 67 ms 191016 KB ok
39 Correct 67 ms 191120 KB ok
40 Correct 66 ms 191056 KB ok
41 Correct 71 ms 191312 KB ok
42 Correct 132 ms 267092 KB ok
43 Correct 133 ms 267984 KB ok
44 Correct 121 ms 264784 KB ok
45 Correct 110 ms 264272 KB ok
46 Correct 133 ms 266088 KB ok
47 Correct 104 ms 263760 KB ok
48 Correct 102 ms 261840 KB ok
49 Correct 104 ms 261728 KB ok
50 Correct 119 ms 263760 KB ok
51 Correct 110 ms 264980 KB ok
52 Correct 113 ms 257032 KB ok
53 Correct 102 ms 254292 KB ok
54 Correct 106 ms 257108 KB ok
55 Correct 116 ms 259864 KB ok
56 Correct 111 ms 257364 KB ok
57 Correct 112 ms 267772 KB ok
58 Correct 120 ms 268372 KB ok
59 Correct 120 ms 268884 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 189384 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 68 ms 189272 KB ok
4 Correct 67 ms 189780 KB ok
5 Correct 65 ms 189780 KB ok
6 Correct 68 ms 189268 KB ok
7 Correct 64 ms 189264 KB ok
8 Correct 69 ms 198480 KB ok
9 Correct 103 ms 263676 KB ok
10 Correct 490 ms 675668 KB ok
11 Correct 69 ms 189264 KB ok
12 Correct 74 ms 189200 KB ok
13 Correct 65 ms 189268 KB ok
14 Correct 65 ms 189268 KB ok
15 Correct 68 ms 189264 KB ok
16 Correct 76 ms 189268 KB ok
17 Correct 76 ms 189224 KB ok
18 Correct 67 ms 189248 KB ok
19 Correct 68 ms 189352 KB ok
20 Correct 67 ms 189380 KB ok
21 Correct 68 ms 189336 KB ok
22 Correct 68 ms 189524 KB ok
23 Correct 66 ms 189524 KB ok
24 Correct 83 ms 189516 KB ok
25 Correct 65 ms 189528 KB ok
26 Correct 66 ms 189524 KB ok
27 Correct 70 ms 189592 KB ok
28 Correct 66 ms 189496 KB ok
29 Correct 71 ms 189420 KB ok
30 Correct 68 ms 189448 KB ok
31 Correct 65 ms 189584 KB ok
32 Correct 66 ms 189592 KB ok
33 Correct 66 ms 189520 KB ok
34 Correct 65 ms 189524 KB ok
35 Correct 65 ms 191312 KB ok
36 Correct 75 ms 191312 KB ok
37 Correct 65 ms 191316 KB ok
38 Correct 69 ms 191316 KB ok
39 Correct 67 ms 191284 KB ok
40 Correct 66 ms 190988 KB ok
41 Correct 67 ms 191104 KB ok
42 Correct 68 ms 191056 KB ok
43 Correct 67 ms 191016 KB ok
44 Correct 67 ms 191120 KB ok
45 Correct 66 ms 191056 KB ok
46 Correct 71 ms 191312 KB ok
47 Correct 132 ms 267092 KB ok
48 Correct 133 ms 267984 KB ok
49 Correct 121 ms 264784 KB ok
50 Correct 110 ms 264272 KB ok
51 Correct 133 ms 266088 KB ok
52 Correct 104 ms 263760 KB ok
53 Correct 102 ms 261840 KB ok
54 Correct 104 ms 261728 KB ok
55 Correct 119 ms 263760 KB ok
56 Correct 110 ms 264980 KB ok
57 Correct 113 ms 257032 KB ok
58 Correct 102 ms 254292 KB ok
59 Correct 106 ms 257108 KB ok
60 Correct 116 ms 259864 KB ok
61 Correct 111 ms 257364 KB ok
62 Correct 112 ms 267772 KB ok
63 Correct 120 ms 268372 KB ok
64 Correct 120 ms 268884 KB ok
65 Correct 1343 ms 728556 KB ok
66 Correct 874 ms 731880 KB ok
67 Correct 588 ms 701700 KB ok
68 Correct 631 ms 678224 KB ok
69 Correct 832 ms 690040 KB ok
70 Correct 944 ms 700000 KB ok
71 Correct 598 ms 677456 KB ok
72 Correct 490 ms 675896 KB ok
73 Correct 570 ms 668244 KB ok
74 Correct 565 ms 668744 KB ok
75 Correct 570 ms 668584 KB ok
76 Correct 537 ms 675920 KB ok
77 Correct 537 ms 675924 KB ok
78 Correct 667 ms 686616 KB ok
79 Correct 555 ms 680468 KB ok
80 Correct 531 ms 678756 KB ok
81 Correct 530 ms 678824 KB ok
82 Correct 583 ms 682836 KB ok
83 Correct 677 ms 695924 KB ok
84 Correct 720 ms 629732 KB ok
85 Correct 470 ms 623184 KB ok
86 Correct 766 ms 634280 KB ok
87 Correct 4258 ms 637416 KB ok
88 Correct 469 ms 651344 KB ok
89 Correct 515 ms 683724 KB ok
90 Correct 496 ms 683604 KB ok
91 Correct 497 ms 681552 KB ok
92 Correct 599 ms 697240 KB ok
93 Correct 631 ms 699788 KB ok
94 Correct 511 ms 688840 KB ok
95 Correct 508 ms 686284 KB ok
96 Correct 494 ms 685512 KB ok
97 Correct 586 ms 684764 KB ok
98 Correct 459 ms 681292 KB ok
99 Correct 1072 ms 749164 KB ok
100 Correct 576 ms 746580 KB ok
101 Correct 575 ms 740440 KB ok
102 Correct 572 ms 746576 KB ok
103 Correct 668 ms 757328 KB ok
104 Correct 629 ms 761304 KB ok
105 Correct 606 ms 764244 KB ok
106 Correct 646 ms 767284 KB ok
107 Correct 631 ms 766800 KB ok
108 Correct 543 ms 688588 KB ok
109 Correct 539 ms 688844 KB ok