oj.uz

Submission #1017140

# Submission time Handle Problem Language Result Execution time Memory
1017140 2024-07-08T22:23:13 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 731820 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);
      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 67 ms 189460 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189316 KB ok
2 Correct 65 ms 189264 KB ok
3 Correct 68 ms 189728 KB ok
4 Correct 67 ms 189872 KB ok
5 Correct 68 ms 189212 KB ok
6 Correct 70 ms 189268 KB ok
7 Correct 72 ms 198420 KB ok
8 Correct 137 ms 263640 KB ok
9 Correct 522 ms 675664 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 189316 KB ok
2 Correct 65 ms 189264 KB ok
3 Correct 82 ms 189276 KB ok
4 Correct 68 ms 189268 KB ok
5 Correct 71 ms 189404 KB ok
6 Correct 79 ms 189264 KB ok
7 Correct 70 ms 189268 KB ok
8 Correct 65 ms 189300 KB ok
9 Correct 64 ms 189264 KB ok
10 Correct 67 ms 189268 KB ok
11 Correct 81 ms 189288 KB ok
12 Correct 69 ms 189264 KB ok
13 Correct 70 ms 189268 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189460 KB ok
2 Correct 66 ms 189316 KB ok
3 Correct 65 ms 189264 KB ok
4 Correct 82 ms 189276 KB ok
5 Correct 68 ms 189268 KB ok
6 Correct 71 ms 189404 KB ok
7 Correct 79 ms 189264 KB ok
8 Correct 70 ms 189268 KB ok
9 Correct 65 ms 189300 KB ok
10 Correct 64 ms 189264 KB ok
11 Correct 67 ms 189268 KB ok
12 Correct 81 ms 189288 KB ok
13 Correct 69 ms 189264 KB ok
14 Correct 70 ms 189268 KB ok
15 Correct 67 ms 189540 KB ok
16 Correct 67 ms 189524 KB ok
17 Correct 65 ms 189516 KB ok
18 Correct 71 ms 189524 KB ok
19 Correct 67 ms 189520 KB ok
20 Correct 64 ms 189408 KB ok
21 Correct 67 ms 189524 KB ok
22 Correct 65 ms 189524 KB ok
23 Correct 67 ms 189520 KB ok
24 Correct 68 ms 189528 KB ok
25 Correct 65 ms 189520 KB ok
26 Correct 82 ms 189524 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189460 KB ok
2 Correct 66 ms 189316 KB ok
3 Correct 65 ms 189264 KB ok
4 Correct 68 ms 189728 KB ok
5 Correct 67 ms 189872 KB ok
6 Correct 82 ms 189276 KB ok
7 Correct 68 ms 189268 KB ok
8 Correct 71 ms 189404 KB ok
9 Correct 79 ms 189264 KB ok
10 Correct 70 ms 189268 KB ok
11 Correct 65 ms 189300 KB ok
12 Correct 64 ms 189264 KB ok
13 Correct 67 ms 189268 KB ok
14 Correct 81 ms 189288 KB ok
15 Correct 69 ms 189264 KB ok
16 Correct 70 ms 189268 KB ok
17 Correct 67 ms 189540 KB ok
18 Correct 67 ms 189524 KB ok
19 Correct 65 ms 189516 KB ok
20 Correct 71 ms 189524 KB ok
21 Correct 67 ms 189520 KB ok
22 Correct 64 ms 189408 KB ok
23 Correct 67 ms 189524 KB ok
24 Correct 65 ms 189524 KB ok
25 Correct 67 ms 189520 KB ok
26 Correct 68 ms 189528 KB ok
27 Correct 65 ms 189520 KB ok
28 Correct 82 ms 189524 KB ok
29 Correct 71 ms 189404 KB ok
30 Correct 70 ms 191336 KB ok
31 Correct 67 ms 191312 KB ok
32 Correct 65 ms 191376 KB ok
33 Correct 70 ms 191144 KB ok
34 Correct 67 ms 191196 KB ok
35 Correct 68 ms 191056 KB ok
36 Correct 67 ms 191160 KB ok
37 Correct 66 ms 191056 KB ok
38 Correct 66 ms 191056 KB ok
39 Correct 69 ms 191104 KB ok
40 Correct 68 ms 191060 KB ok
41 Correct 65 ms 191248 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189460 KB ok
2 Correct 66 ms 189316 KB ok
3 Correct 65 ms 189264 KB ok
4 Correct 68 ms 189728 KB ok
5 Correct 67 ms 189872 KB ok
6 Correct 82 ms 189276 KB ok
7 Correct 68 ms 189268 KB ok
8 Correct 71 ms 189404 KB ok
9 Correct 79 ms 189264 KB ok
10 Correct 70 ms 189268 KB ok
11 Correct 65 ms 189300 KB ok
12 Correct 64 ms 189264 KB ok
13 Correct 67 ms 189268 KB ok
14 Correct 81 ms 189288 KB ok
15 Correct 69 ms 189264 KB ok
16 Correct 70 ms 189268 KB ok
17 Correct 67 ms 189540 KB ok
18 Correct 67 ms 189524 KB ok
19 Correct 65 ms 189516 KB ok
20 Correct 71 ms 189524 KB ok
21 Correct 67 ms 189520 KB ok
22 Correct 64 ms 189408 KB ok
23 Correct 67 ms 189524 KB ok
24 Correct 65 ms 189524 KB ok
25 Correct 67 ms 189520 KB ok
26 Correct 68 ms 189528 KB ok
27 Correct 65 ms 189520 KB ok
28 Correct 82 ms 189524 KB ok
29 Correct 71 ms 189404 KB ok
30 Correct 70 ms 191336 KB ok
31 Correct 67 ms 191312 KB ok
32 Correct 65 ms 191376 KB ok
33 Correct 70 ms 191144 KB ok
34 Correct 67 ms 191196 KB ok
35 Correct 68 ms 191056 KB ok
36 Correct 67 ms 191160 KB ok
37 Correct 66 ms 191056 KB ok
38 Correct 66 ms 191056 KB ok
39 Correct 69 ms 191104 KB ok
40 Correct 68 ms 191060 KB ok
41 Correct 65 ms 191248 KB ok
42 Correct 128 ms 267088 KB ok
43 Correct 138 ms 268088 KB ok
44 Correct 119 ms 264976 KB ok
45 Correct 115 ms 264272 KB ok
46 Correct 130 ms 266064 KB ok
47 Correct 106 ms 263764 KB ok
48 Correct 104 ms 261724 KB ok
49 Correct 101 ms 261676 KB ok
50 Correct 107 ms 263764 KB ok
51 Correct 106 ms 264784 KB ok
52 Correct 104 ms 256848 KB ok
53 Correct 101 ms 254292 KB ok
54 Correct 110 ms 257552 KB ok
55 Correct 114 ms 260068 KB ok
56 Correct 104 ms 257348 KB ok
57 Correct 117 ms 267856 KB ok
58 Correct 124 ms 268372 KB ok
59 Correct 123 ms 268932 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189460 KB ok
2 Correct 66 ms 189316 KB ok
3 Correct 65 ms 189264 KB ok
4 Correct 68 ms 189728 KB ok
5 Correct 67 ms 189872 KB ok
6 Correct 68 ms 189212 KB ok
7 Correct 70 ms 189268 KB ok
8 Correct 72 ms 198420 KB ok
9 Correct 137 ms 263640 KB ok
10 Correct 522 ms 675664 KB ok
11 Correct 82 ms 189276 KB ok
12 Correct 68 ms 189268 KB ok
13 Correct 71 ms 189404 KB ok
14 Correct 79 ms 189264 KB ok
15 Correct 70 ms 189268 KB ok
16 Correct 65 ms 189300 KB ok
17 Correct 64 ms 189264 KB ok
18 Correct 67 ms 189268 KB ok
19 Correct 81 ms 189288 KB ok
20 Correct 69 ms 189264 KB ok
21 Correct 70 ms 189268 KB ok
22 Correct 67 ms 189540 KB ok
23 Correct 67 ms 189524 KB ok
24 Correct 65 ms 189516 KB ok
25 Correct 71 ms 189524 KB ok
26 Correct 67 ms 189520 KB ok
27 Correct 64 ms 189408 KB ok
28 Correct 67 ms 189524 KB ok
29 Correct 65 ms 189524 KB ok
30 Correct 67 ms 189520 KB ok
31 Correct 68 ms 189528 KB ok
32 Correct 65 ms 189520 KB ok
33 Correct 82 ms 189524 KB ok
34 Correct 71 ms 189404 KB ok
35 Correct 70 ms 191336 KB ok
36 Correct 67 ms 191312 KB ok
37 Correct 65 ms 191376 KB ok
38 Correct 70 ms 191144 KB ok
39 Correct 67 ms 191196 KB ok
40 Correct 68 ms 191056 KB ok
41 Correct 67 ms 191160 KB ok
42 Correct 66 ms 191056 KB ok
43 Correct 66 ms 191056 KB ok
44 Correct 69 ms 191104 KB ok
45 Correct 68 ms 191060 KB ok
46 Correct 65 ms 191248 KB ok
47 Correct 128 ms 267088 KB ok
48 Correct 138 ms 268088 KB ok
49 Correct 119 ms 264976 KB ok
50 Correct 115 ms 264272 KB ok
51 Correct 130 ms 266064 KB ok
52 Correct 106 ms 263764 KB ok
53 Correct 104 ms 261724 KB ok
54 Correct 101 ms 261676 KB ok
55 Correct 107 ms 263764 KB ok
56 Correct 106 ms 264784 KB ok
57 Correct 104 ms 256848 KB ok
58 Correct 101 ms 254292 KB ok
59 Correct 110 ms 257552 KB ok
60 Correct 114 ms 260068 KB ok
61 Correct 104 ms 257348 KB ok
62 Correct 117 ms 267856 KB ok
63 Correct 124 ms 268372 KB ok
64 Correct 123 ms 268932 KB ok
65 Correct 1071 ms 728336 KB ok
66 Correct 801 ms 731820 KB ok
67 Correct 582 ms 701748 KB ok
68 Correct 623 ms 678228 KB ok
69 Correct 773 ms 690124 KB ok
70 Correct 858 ms 699848 KB ok
71 Correct 570 ms 677032 KB ok
72 Correct 501 ms 675664 KB ok
73 Correct 548 ms 668504 KB ok
74 Correct 509 ms 669100 KB ok
75 Correct 570 ms 668940 KB ok
76 Correct 505 ms 675920 KB ok
77 Correct 530 ms 676004 KB ok
78 Correct 724 ms 686816 KB ok
79 Correct 517 ms 680392 KB ok
80 Correct 497 ms 678860 KB ok
81 Correct 513 ms 678820 KB ok
82 Correct 584 ms 682628 KB ok
83 Correct 650 ms 695988 KB ok
84 Correct 782 ms 629752 KB ok
85 Correct 501 ms 623268 KB ok
86 Correct 777 ms 634132 KB ok
87 Execution timed out 4553 ms 637268 KB Time limit exceeded
88 Halted 0 ms 0 KB -