oj.uz

답안 #1017127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017127 2024-07-08T22:00:50 Z MilosMilutinovic 축구 경기장 (IOI23_soccer) C++17
70 / 100
 4500 ms 579220 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 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 16732 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 4 ms 30556 KB ok
8 Correct 33 ms 66268 KB ok
9 Correct 487 ms 518960 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 KB ok
2 Correct 3 ms 20828 KB ok
3 Correct 2 ms 20828 KB ok
4 Correct 2 ms 20928 KB ok
5 Correct 2 ms 20828 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 20824 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20828 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 KB ok
2 Correct 2 ms 20824 KB ok
3 Correct 3 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20928 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 2 ms 20824 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 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 20828 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 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 20828 KB ok
26 Correct 2 ms 20828 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 KB ok
2 Correct 2 ms 20824 KB ok
3 Correct 3 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20828 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20928 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 20824 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20828 KB ok
14 Correct 2 ms 20824 KB ok
15 Correct 2 ms 20828 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 20828 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 20828 KB ok
26 Correct 2 ms 20828 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 25428 KB ok
31 Correct 3 ms 27228 KB ok
32 Correct 3 ms 27228 KB ok
33 Correct 3 ms 27228 KB ok
34 Correct 3 ms 27228 KB ok
35 Correct 2 ms 25180 KB ok
36 Correct 3 ms 27228 KB ok
37 Correct 3 ms 27228 KB ok
38 Correct 2 ms 27124 KB ok
39 Correct 3 ms 27228 KB ok
40 Correct 2 ms 25180 KB ok
41 Correct 2 ms 25180 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 KB ok
2 Correct 2 ms 20824 KB ok
3 Correct 3 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20828 KB ok
6 Correct 2 ms 20828 KB ok
7 Correct 2 ms 20928 KB ok
8 Correct 2 ms 20828 KB ok
9 Correct 2 ms 20828 KB ok
10 Correct 2 ms 20824 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20828 KB ok
13 Correct 2 ms 20828 KB ok
14 Correct 2 ms 20824 KB ok
15 Correct 2 ms 20828 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 20828 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 20828 KB ok
26 Correct 2 ms 20828 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 25428 KB ok
31 Correct 3 ms 27228 KB ok
32 Correct 3 ms 27228 KB ok
33 Correct 3 ms 27228 KB ok
34 Correct 3 ms 27228 KB ok
35 Correct 2 ms 25180 KB ok
36 Correct 3 ms 27228 KB ok
37 Correct 3 ms 27228 KB ok
38 Correct 2 ms 27124 KB ok
39 Correct 3 ms 27228 KB ok
40 Correct 2 ms 25180 KB ok
41 Correct 2 ms 25180 KB ok
42 Correct 95 ms 68884 KB ok
43 Correct 97 ms 70084 KB ok
44 Correct 76 ms 66392 KB ok
45 Correct 64 ms 65872 KB ok
46 Correct 84 ms 67792 KB ok
47 Correct 35 ms 63568 KB ok
48 Correct 44 ms 63128 KB ok
49 Correct 39 ms 63060 KB ok
50 Correct 56 ms 66504 KB ok
51 Correct 48 ms 66764 KB ok
52 Correct 57 ms 58160 KB ok
53 Correct 34 ms 59472 KB ok
54 Correct 57 ms 59732 KB ok
55 Correct 84 ms 61736 KB ok
56 Correct 33 ms 59920 KB ok
57 Correct 58 ms 69552 KB ok
58 Correct 66 ms 69968 KB ok
59 Correct 75 ms 70492 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 20824 KB ok
2 Correct 2 ms 20824 KB ok
3 Correct 3 ms 20828 KB ok
4 Correct 2 ms 20828 KB ok
5 Correct 2 ms 20828 KB ok
6 Correct 2 ms 16732 KB ok
7 Correct 2 ms 20828 KB ok
8 Correct 4 ms 30556 KB ok
9 Correct 33 ms 66268 KB ok
10 Correct 487 ms 518960 KB ok
11 Correct 2 ms 20828 KB ok
12 Correct 2 ms 20928 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 20824 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 20828 KB ok
26 Correct 2 ms 20828 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 20828 KB ok
33 Correct 2 ms 20828 KB ok
34 Correct 2 ms 20828 KB ok
35 Correct 2 ms 25428 KB ok
36 Correct 3 ms 27228 KB ok
37 Correct 3 ms 27228 KB ok
38 Correct 3 ms 27228 KB ok
39 Correct 3 ms 27228 KB ok
40 Correct 2 ms 25180 KB ok
41 Correct 3 ms 27228 KB ok
42 Correct 3 ms 27228 KB ok
43 Correct 2 ms 27124 KB ok
44 Correct 3 ms 27228 KB ok
45 Correct 2 ms 25180 KB ok
46 Correct 2 ms 25180 KB ok
47 Correct 95 ms 68884 KB ok
48 Correct 97 ms 70084 KB ok
49 Correct 76 ms 66392 KB ok
50 Correct 64 ms 65872 KB ok
51 Correct 84 ms 67792 KB ok
52 Correct 35 ms 63568 KB ok
53 Correct 44 ms 63128 KB ok
54 Correct 39 ms 63060 KB ok
55 Correct 56 ms 66504 KB ok
56 Correct 48 ms 66764 KB ok
57 Correct 57 ms 58160 KB ok
58 Correct 34 ms 59472 KB ok
59 Correct 57 ms 59732 KB ok
60 Correct 84 ms 61736 KB ok
61 Correct 33 ms 59920 KB ok
62 Correct 58 ms 69552 KB ok
63 Correct 66 ms 69968 KB ok
64 Correct 75 ms 70492 KB ok
65 Correct 2025 ms 575148 KB ok
66 Correct 1036 ms 579220 KB ok
67 Correct 660 ms 545388 KB ok
68 Correct 952 ms 521552 KB ok
69 Correct 1346 ms 533696 KB ok
70 Correct 1540 ms 543896 KB ok
71 Correct 806 ms 520528 KB ok
72 Correct 501 ms 518996 KB ok
73 Correct 761 ms 512084 KB ok
74 Correct 745 ms 512452 KB ok
75 Correct 769 ms 512592 KB ok
76 Correct 919 ms 535484 KB ok
77 Correct 948 ms 535484 KB ok
78 Correct 1326 ms 531508 KB ok
79 Correct 567 ms 524228 KB ok
80 Correct 570 ms 522640 KB ok
81 Correct 577 ms 522644 KB ok
82 Correct 869 ms 526532 KB ok
83 Correct 832 ms 541828 KB ok
84 Correct 1912 ms 473424 KB ok
85 Correct 547 ms 466512 KB ok
86 Correct 2069 ms 477780 KB ok
87 Execution timed out 4576 ms 482132 KB Time limit exceeded
88 Halted 0 ms 0 KB -