oj.uz

Submission #1017134

# Submission time Handle Problem Language Result Execution time Memory
1017134 2024-07-08T22:12:02 Z MilosMilutinovic Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 736076 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 65 ms 189520 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 67 ms 189268 KB ok
3 Correct 71 ms 189776 KB ok
4 Correct 64 ms 189776 KB ok
5 Correct 69 ms 189264 KB ok
6 Correct 74 ms 189248 KB ok
7 Correct 69 ms 198328 KB ok
8 Correct 102 ms 263840 KB ok
9 Correct 572 ms 675752 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 67 ms 189268 KB ok
3 Correct 72 ms 189332 KB ok
4 Correct 65 ms 189248 KB ok
5 Correct 69 ms 189268 KB ok
6 Correct 77 ms 189268 KB ok
7 Correct 66 ms 189264 KB ok
8 Correct 77 ms 189268 KB ok
9 Correct 66 ms 189264 KB ok
10 Correct 67 ms 189264 KB ok
11 Correct 64 ms 189352 KB ok
12 Correct 67 ms 189264 KB ok
13 Correct 65 ms 189264 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 67 ms 189268 KB ok
4 Correct 72 ms 189332 KB ok
5 Correct 65 ms 189248 KB ok
6 Correct 69 ms 189268 KB ok
7 Correct 77 ms 189268 KB ok
8 Correct 66 ms 189264 KB ok
9 Correct 77 ms 189268 KB ok
10 Correct 66 ms 189264 KB ok
11 Correct 67 ms 189264 KB ok
12 Correct 64 ms 189352 KB ok
13 Correct 67 ms 189264 KB ok
14 Correct 65 ms 189264 KB ok
15 Correct 73 ms 189520 KB ok
16 Correct 68 ms 189524 KB ok
17 Correct 77 ms 189520 KB ok
18 Correct 71 ms 189520 KB ok
19 Correct 66 ms 189524 KB ok
20 Correct 67 ms 189340 KB ok
21 Correct 72 ms 189632 KB ok
22 Correct 67 ms 189524 KB ok
23 Correct 68 ms 189524 KB ok
24 Correct 67 ms 189520 KB ok
25 Correct 76 ms 189520 KB ok
26 Correct 68 ms 189572 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 67 ms 189268 KB ok
4 Correct 71 ms 189776 KB ok
5 Correct 64 ms 189776 KB ok
6 Correct 72 ms 189332 KB ok
7 Correct 65 ms 189248 KB ok
8 Correct 69 ms 189268 KB ok
9 Correct 77 ms 189268 KB ok
10 Correct 66 ms 189264 KB ok
11 Correct 77 ms 189268 KB ok
12 Correct 66 ms 189264 KB ok
13 Correct 67 ms 189264 KB ok
14 Correct 64 ms 189352 KB ok
15 Correct 67 ms 189264 KB ok
16 Correct 65 ms 189264 KB ok
17 Correct 73 ms 189520 KB ok
18 Correct 68 ms 189524 KB ok
19 Correct 77 ms 189520 KB ok
20 Correct 71 ms 189520 KB ok
21 Correct 66 ms 189524 KB ok
22 Correct 67 ms 189340 KB ok
23 Correct 72 ms 189632 KB ok
24 Correct 67 ms 189524 KB ok
25 Correct 68 ms 189524 KB ok
26 Correct 67 ms 189520 KB ok
27 Correct 76 ms 189520 KB ok
28 Correct 68 ms 189572 KB ok
29 Correct 66 ms 189524 KB ok
30 Correct 67 ms 191312 KB ok
31 Correct 68 ms 191316 KB ok
32 Correct 69 ms 191312 KB ok
33 Correct 66 ms 191312 KB ok
34 Correct 71 ms 191252 KB ok
35 Correct 66 ms 191108 KB ok
36 Correct 69 ms 191060 KB ok
37 Correct 68 ms 191056 KB ok
38 Correct 68 ms 191060 KB ok
39 Correct 65 ms 191208 KB ok
40 Correct 69 ms 191060 KB ok
41 Correct 65 ms 191312 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 67 ms 189268 KB ok
4 Correct 71 ms 189776 KB ok
5 Correct 64 ms 189776 KB ok
6 Correct 72 ms 189332 KB ok
7 Correct 65 ms 189248 KB ok
8 Correct 69 ms 189268 KB ok
9 Correct 77 ms 189268 KB ok
10 Correct 66 ms 189264 KB ok
11 Correct 77 ms 189268 KB ok
12 Correct 66 ms 189264 KB ok
13 Correct 67 ms 189264 KB ok
14 Correct 64 ms 189352 KB ok
15 Correct 67 ms 189264 KB ok
16 Correct 65 ms 189264 KB ok
17 Correct 73 ms 189520 KB ok
18 Correct 68 ms 189524 KB ok
19 Correct 77 ms 189520 KB ok
20 Correct 71 ms 189520 KB ok
21 Correct 66 ms 189524 KB ok
22 Correct 67 ms 189340 KB ok
23 Correct 72 ms 189632 KB ok
24 Correct 67 ms 189524 KB ok
25 Correct 68 ms 189524 KB ok
26 Correct 67 ms 189520 KB ok
27 Correct 76 ms 189520 KB ok
28 Correct 68 ms 189572 KB ok
29 Correct 66 ms 189524 KB ok
30 Correct 67 ms 191312 KB ok
31 Correct 68 ms 191316 KB ok
32 Correct 69 ms 191312 KB ok
33 Correct 66 ms 191312 KB ok
34 Correct 71 ms 191252 KB ok
35 Correct 66 ms 191108 KB ok
36 Correct 69 ms 191060 KB ok
37 Correct 68 ms 191056 KB ok
38 Correct 68 ms 191060 KB ok
39 Correct 65 ms 191208 KB ok
40 Correct 69 ms 191060 KB ok
41 Correct 65 ms 191312 KB ok
42 Correct 138 ms 267208 KB ok
43 Correct 134 ms 268236 KB ok
44 Correct 119 ms 264660 KB ok
45 Correct 117 ms 264360 KB ok
46 Correct 127 ms 266192 KB ok
47 Correct 105 ms 263760 KB ok
48 Correct 216 ms 261712 KB ok
49 Correct 172 ms 261688 KB ok
50 Correct 106 ms 264972 KB ok
51 Correct 125 ms 265168 KB ok
52 Correct 240 ms 256852 KB ok
53 Correct 106 ms 254288 KB ok
54 Correct 222 ms 257108 KB ok
55 Correct 352 ms 259932 KB ok
56 Correct 101 ms 257360 KB ok
57 Correct 553 ms 267796 KB ok
58 Correct 494 ms 268396 KB ok
59 Correct 434 ms 268884 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 67 ms 189268 KB ok
4 Correct 71 ms 189776 KB ok
5 Correct 64 ms 189776 KB ok
6 Correct 69 ms 189264 KB ok
7 Correct 74 ms 189248 KB ok
8 Correct 69 ms 198328 KB ok
9 Correct 102 ms 263840 KB ok
10 Correct 572 ms 675752 KB ok
11 Correct 72 ms 189332 KB ok
12 Correct 65 ms 189248 KB ok
13 Correct 69 ms 189268 KB ok
14 Correct 77 ms 189268 KB ok
15 Correct 66 ms 189264 KB ok
16 Correct 77 ms 189268 KB ok
17 Correct 66 ms 189264 KB ok
18 Correct 67 ms 189264 KB ok
19 Correct 64 ms 189352 KB ok
20 Correct 67 ms 189264 KB ok
21 Correct 65 ms 189264 KB ok
22 Correct 73 ms 189520 KB ok
23 Correct 68 ms 189524 KB ok
24 Correct 77 ms 189520 KB ok
25 Correct 71 ms 189520 KB ok
26 Correct 66 ms 189524 KB ok
27 Correct 67 ms 189340 KB ok
28 Correct 72 ms 189632 KB ok
29 Correct 67 ms 189524 KB ok
30 Correct 68 ms 189524 KB ok
31 Correct 67 ms 189520 KB ok
32 Correct 76 ms 189520 KB ok
33 Correct 68 ms 189572 KB ok
34 Correct 66 ms 189524 KB ok
35 Correct 67 ms 191312 KB ok
36 Correct 68 ms 191316 KB ok
37 Correct 69 ms 191312 KB ok
38 Correct 66 ms 191312 KB ok
39 Correct 71 ms 191252 KB ok
40 Correct 66 ms 191108 KB ok
41 Correct 69 ms 191060 KB ok
42 Correct 68 ms 191056 KB ok
43 Correct 68 ms 191060 KB ok
44 Correct 65 ms 191208 KB ok
45 Correct 69 ms 191060 KB ok
46 Correct 65 ms 191312 KB ok
47 Correct 138 ms 267208 KB ok
48 Correct 134 ms 268236 KB ok
49 Correct 119 ms 264660 KB ok
50 Correct 117 ms 264360 KB ok
51 Correct 127 ms 266192 KB ok
52 Correct 105 ms 263760 KB ok
53 Correct 216 ms 261712 KB ok
54 Correct 172 ms 261688 KB ok
55 Correct 106 ms 264972 KB ok
56 Correct 125 ms 265168 KB ok
57 Correct 240 ms 256852 KB ok
58 Correct 106 ms 254288 KB ok
59 Correct 222 ms 257108 KB ok
60 Correct 352 ms 259932 KB ok
61 Correct 101 ms 257360 KB ok
62 Correct 553 ms 267796 KB ok
63 Correct 494 ms 268396 KB ok
64 Correct 434 ms 268884 KB ok
65 Correct 958 ms 732076 KB ok
66 Correct 681 ms 736076 KB ok
67 Correct 560 ms 702204 KB ok
68 Correct 666 ms 678364 KB ok
69 Correct 900 ms 690560 KB ok
70 Correct 943 ms 700864 KB ok
71 Correct 582 ms 677200 KB ok
72 Correct 519 ms 675920 KB ok
73 Execution timed out 4580 ms 668448 KB Time limit exceeded
74 Halted 0 ms 0 KB -