oj.uz

Submission #1017126

# Submission time Handle Problem Language Result Execution time Memory
1017126 2024-07-08T21:57:59 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 579176 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, 4>, 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 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);
      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;
    }
  }
  sort(to.begin(), to.end(), [&](array<int, 5> a, array<int, 5> b) {
    int val_a = ((a[3] == yl || a[4] == yr) ? 0 : 1);
    int val_b = ((b[3] == yl || b[4] == yr) ? 0 : 1);
    return val_a > val_b;
  });
  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[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];
    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 2 ms 20984 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB ok
2 Correct 2 ms 20828 KB ok
3 Correct 2 ms 20824 KB ok
4 Correct 2 ms 20924 KB ok
5 Correct 1 ms 16732 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 5 ms 26744 KB ok
8 Correct 52 ms 66388 KB ok
9 Correct 515 ms 518940 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 20828 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 21080 KB ok
10 Correct 2 ms 20984 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 20984 KB ok
2 Correct 3 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 20828 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 21080 KB ok
11 Correct 2 ms 20984 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 20824 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 20916 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 20940 KB ok
26 Correct 2 ms 20824 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20984 KB ok
2 Correct 3 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20824 KB ok
5 Correct 2 ms 20924 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20824 KB ok
8 Correct 2 ms 20828 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 21080 KB ok
13 Correct 2 ms 20984 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 20916 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 20940 KB ok
28 Correct 2 ms 20824 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 3 ms 31068 KB ok
31 Correct 3 ms 29276 KB ok
32 Correct 3 ms 25180 KB ok
33 Correct 3 ms 31068 KB ok
34 Correct 3 ms 29276 KB ok
35 Correct 3 ms 29276 KB ok
36 Correct 3 ms 31068 KB ok
37 Correct 3 ms 31064 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 29168 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 29180 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20984 KB ok
2 Correct 3 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20824 KB ok
5 Correct 2 ms 20924 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20824 KB ok
8 Correct 2 ms 20828 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 21080 KB ok
13 Correct 2 ms 20984 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 20916 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 20940 KB ok
28 Correct 2 ms 20824 KB ok
29 Correct 2 ms 20828 KB ok
30 Correct 3 ms 31068 KB ok
31 Correct 3 ms 29276 KB ok
32 Correct 3 ms 25180 KB ok
33 Correct 3 ms 31068 KB ok
34 Correct 3 ms 29276 KB ok
35 Correct 3 ms 29276 KB ok
36 Correct 3 ms 31068 KB ok
37 Correct 3 ms 31064 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 29168 KB ok
40 Correct 3 ms 31068 KB ok
41 Correct 3 ms 29180 KB ok
42 Correct 117 ms 69752 KB ok
43 Correct 116 ms 70796 KB ok
44 Correct 87 ms 67152 KB ok
45 Correct 107 ms 67300 KB ok
46 Correct 97 ms 69124 KB ok
47 Correct 44 ms 66280 KB ok
48 Correct 67 ms 63828 KB ok
49 Correct 40 ms 63704 KB ok
50 Correct 72 ms 67596 KB ok
51 Correct 49 ms 68296 KB ok
52 Correct 127 ms 62032 KB ok
53 Correct 36 ms 63064 KB ok
54 Correct 118 ms 63568 KB ok
55 Correct 111 ms 64668 KB ok
56 Correct 40 ms 63568 KB ok
57 Correct 61 ms 70420 KB ok
58 Correct 76 ms 71504 KB ok
59 Correct 72 ms 72136 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20984 KB ok
2 Correct 3 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20824 KB ok
5 Correct 2 ms 20924 KB ok
6 Correct 1 ms 16732 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 5 ms 26744 KB ok
9 Correct 52 ms 66388 KB ok
10 Correct 515 ms 518940 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 21080 KB ok
18 Correct 2 ms 20984 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 20824 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 20916 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 20940 KB ok
33 Correct 2 ms 20824 KB ok
34 Correct 2 ms 20828 KB ok
35 Correct 3 ms 31068 KB ok
36 Correct 3 ms 29276 KB ok
37 Correct 3 ms 25180 KB ok
38 Correct 3 ms 31068 KB ok
39 Correct 3 ms 29276 KB ok
40 Correct 3 ms 29276 KB ok
41 Correct 3 ms 31068 KB ok
42 Correct 3 ms 31064 KB ok
43 Correct 3 ms 31068 KB ok
44 Correct 3 ms 29168 KB ok
45 Correct 3 ms 31068 KB ok
46 Correct 3 ms 29180 KB ok
47 Correct 117 ms 69752 KB ok
48 Correct 116 ms 70796 KB ok
49 Correct 87 ms 67152 KB ok
50 Correct 107 ms 67300 KB ok
51 Correct 97 ms 69124 KB ok
52 Correct 44 ms 66280 KB ok
53 Correct 67 ms 63828 KB ok
54 Correct 40 ms 63704 KB ok
55 Correct 72 ms 67596 KB ok
56 Correct 49 ms 68296 KB ok
57 Correct 127 ms 62032 KB ok
58 Correct 36 ms 63064 KB ok
59 Correct 118 ms 63568 KB ok
60 Correct 111 ms 64668 KB ok
61 Correct 40 ms 63568 KB ok
62 Correct 61 ms 70420 KB ok
63 Correct 76 ms 71504 KB ok
64 Correct 72 ms 72136 KB ok
65 Correct 2681 ms 575120 KB ok
66 Correct 1217 ms 579176 KB ok
67 Correct 724 ms 545480 KB ok
68 Correct 1246 ms 521524 KB ok
69 Correct 1736 ms 533440 KB ok
70 Correct 2052 ms 543884 KB ok
71 Correct 993 ms 520276 KB ok
72 Correct 551 ms 518940 KB ok
73 Correct 767 ms 512028 KB ok
74 Correct 747 ms 512340 KB ok
75 Correct 703 ms 512564 KB ok
76 Correct 1078 ms 535444 KB ok
77 Correct 997 ms 535484 KB ok
78 Correct 1169 ms 531412 KB ok
79 Correct 574 ms 524272 KB ok
80 Correct 555 ms 522692 KB ok
81 Correct 599 ms 522692 KB ok
82 Correct 941 ms 526532 KB ok
83 Correct 927 ms 542064 KB ok
84 Correct 1330 ms 473376 KB ok
85 Correct 560 ms 466460 KB ok
86 Correct 2260 ms 477904 KB ok
87 Execution timed out 4577 ms 482296 KB Time limit exceeded
88 Halted 0 ms 0 KB -