oj.uz

답안 #1017139

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

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 65 ms 189268 KB ok
3 Correct 67 ms 189828 KB ok
4 Correct 66 ms 189776 KB ok
5 Correct 67 ms 189268 KB ok
6 Correct 67 ms 189272 KB ok
7 Correct 68 ms 198480 KB ok
8 Correct 104 ms 263760 KB ok
9 Correct 539 ms 675664 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 189264 KB ok
2 Correct 65 ms 189268 KB ok
3 Correct 69 ms 189268 KB ok
4 Correct 66 ms 189316 KB ok
5 Correct 66 ms 189268 KB ok
6 Correct 66 ms 189360 KB ok
7 Correct 65 ms 189260 KB ok
8 Correct 71 ms 189304 KB ok
9 Correct 68 ms 189264 KB ok
10 Correct 64 ms 189268 KB ok
11 Correct 66 ms 189268 KB ok
12 Correct 80 ms 189268 KB ok
13 Correct 63 ms 189264 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 65 ms 189268 KB ok
4 Correct 69 ms 189268 KB ok
5 Correct 66 ms 189316 KB ok
6 Correct 66 ms 189268 KB ok
7 Correct 66 ms 189360 KB ok
8 Correct 65 ms 189260 KB ok
9 Correct 71 ms 189304 KB ok
10 Correct 68 ms 189264 KB ok
11 Correct 64 ms 189268 KB ok
12 Correct 66 ms 189268 KB ok
13 Correct 80 ms 189268 KB ok
14 Correct 63 ms 189264 KB ok
15 Correct 64 ms 189520 KB ok
16 Correct 66 ms 189472 KB ok
17 Correct 65 ms 189576 KB ok
18 Correct 78 ms 189524 KB ok
19 Correct 67 ms 189508 KB ok
20 Correct 80 ms 189524 KB ok
21 Correct 68 ms 189452 KB ok
22 Correct 79 ms 189520 KB ok
23 Correct 67 ms 189408 KB ok
24 Correct 65 ms 189432 KB ok
25 Correct 66 ms 189520 KB ok
26 Correct 68 ms 189552 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 65 ms 189268 KB ok
4 Correct 67 ms 189828 KB ok
5 Correct 66 ms 189776 KB ok
6 Correct 69 ms 189268 KB ok
7 Correct 66 ms 189316 KB ok
8 Correct 66 ms 189268 KB ok
9 Correct 66 ms 189360 KB ok
10 Correct 65 ms 189260 KB ok
11 Correct 71 ms 189304 KB ok
12 Correct 68 ms 189264 KB ok
13 Correct 64 ms 189268 KB ok
14 Correct 66 ms 189268 KB ok
15 Correct 80 ms 189268 KB ok
16 Correct 63 ms 189264 KB ok
17 Correct 64 ms 189520 KB ok
18 Correct 66 ms 189472 KB ok
19 Correct 65 ms 189576 KB ok
20 Correct 78 ms 189524 KB ok
21 Correct 67 ms 189508 KB ok
22 Correct 80 ms 189524 KB ok
23 Correct 68 ms 189452 KB ok
24 Correct 79 ms 189520 KB ok
25 Correct 67 ms 189408 KB ok
26 Correct 65 ms 189432 KB ok
27 Correct 66 ms 189520 KB ok
28 Correct 68 ms 189552 KB ok
29 Correct 66 ms 189580 KB ok
30 Correct 70 ms 191312 KB ok
31 Correct 82 ms 191336 KB ok
32 Correct 66 ms 191312 KB ok
33 Correct 79 ms 191248 KB ok
34 Correct 66 ms 191316 KB ok
35 Correct 71 ms 191060 KB ok
36 Correct 68 ms 191084 KB ok
37 Correct 67 ms 191056 KB ok
38 Correct 66 ms 191056 KB ok
39 Correct 65 ms 191060 KB ok
40 Correct 81 ms 191156 KB ok
41 Correct 65 ms 191316 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 65 ms 189268 KB ok
4 Correct 67 ms 189828 KB ok
5 Correct 66 ms 189776 KB ok
6 Correct 69 ms 189268 KB ok
7 Correct 66 ms 189316 KB ok
8 Correct 66 ms 189268 KB ok
9 Correct 66 ms 189360 KB ok
10 Correct 65 ms 189260 KB ok
11 Correct 71 ms 189304 KB ok
12 Correct 68 ms 189264 KB ok
13 Correct 64 ms 189268 KB ok
14 Correct 66 ms 189268 KB ok
15 Correct 80 ms 189268 KB ok
16 Correct 63 ms 189264 KB ok
17 Correct 64 ms 189520 KB ok
18 Correct 66 ms 189472 KB ok
19 Correct 65 ms 189576 KB ok
20 Correct 78 ms 189524 KB ok
21 Correct 67 ms 189508 KB ok
22 Correct 80 ms 189524 KB ok
23 Correct 68 ms 189452 KB ok
24 Correct 79 ms 189520 KB ok
25 Correct 67 ms 189408 KB ok
26 Correct 65 ms 189432 KB ok
27 Correct 66 ms 189520 KB ok
28 Correct 68 ms 189552 KB ok
29 Correct 66 ms 189580 KB ok
30 Correct 70 ms 191312 KB ok
31 Correct 82 ms 191336 KB ok
32 Correct 66 ms 191312 KB ok
33 Correct 79 ms 191248 KB ok
34 Correct 66 ms 191316 KB ok
35 Correct 71 ms 191060 KB ok
36 Correct 68 ms 191084 KB ok
37 Correct 67 ms 191056 KB ok
38 Correct 66 ms 191056 KB ok
39 Correct 65 ms 191060 KB ok
40 Correct 81 ms 191156 KB ok
41 Correct 65 ms 191316 KB ok
42 Correct 129 ms 267088 KB ok
43 Correct 129 ms 267980 KB ok
44 Correct 121 ms 264788 KB ok
45 Correct 122 ms 264208 KB ok
46 Correct 131 ms 266068 KB ok
47 Correct 104 ms 263724 KB ok
48 Correct 124 ms 261968 KB ok
49 Correct 106 ms 261716 KB ok
50 Correct 108 ms 263760 KB ok
51 Correct 118 ms 264784 KB ok
52 Correct 106 ms 256936 KB ok
53 Correct 109 ms 254452 KB ok
54 Correct 111 ms 257108 KB ok
55 Correct 112 ms 260048 KB ok
56 Correct 107 ms 257348 KB ok
57 Correct 121 ms 267856 KB ok
58 Correct 119 ms 268428 KB ok
59 Correct 120 ms 268984 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 189520 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 65 ms 189268 KB ok
4 Correct 67 ms 189828 KB ok
5 Correct 66 ms 189776 KB ok
6 Correct 67 ms 189268 KB ok
7 Correct 67 ms 189272 KB ok
8 Correct 68 ms 198480 KB ok
9 Correct 104 ms 263760 KB ok
10 Correct 539 ms 675664 KB ok
11 Correct 69 ms 189268 KB ok
12 Correct 66 ms 189316 KB ok
13 Correct 66 ms 189268 KB ok
14 Correct 66 ms 189360 KB ok
15 Correct 65 ms 189260 KB ok
16 Correct 71 ms 189304 KB ok
17 Correct 68 ms 189264 KB ok
18 Correct 64 ms 189268 KB ok
19 Correct 66 ms 189268 KB ok
20 Correct 80 ms 189268 KB ok
21 Correct 63 ms 189264 KB ok
22 Correct 64 ms 189520 KB ok
23 Correct 66 ms 189472 KB ok
24 Correct 65 ms 189576 KB ok
25 Correct 78 ms 189524 KB ok
26 Correct 67 ms 189508 KB ok
27 Correct 80 ms 189524 KB ok
28 Correct 68 ms 189452 KB ok
29 Correct 79 ms 189520 KB ok
30 Correct 67 ms 189408 KB ok
31 Correct 65 ms 189432 KB ok
32 Correct 66 ms 189520 KB ok
33 Correct 68 ms 189552 KB ok
34 Correct 66 ms 189580 KB ok
35 Correct 70 ms 191312 KB ok
36 Correct 82 ms 191336 KB ok
37 Correct 66 ms 191312 KB ok
38 Correct 79 ms 191248 KB ok
39 Correct 66 ms 191316 KB ok
40 Correct 71 ms 191060 KB ok
41 Correct 68 ms 191084 KB ok
42 Correct 67 ms 191056 KB ok
43 Correct 66 ms 191056 KB ok
44 Correct 65 ms 191060 KB ok
45 Correct 81 ms 191156 KB ok
46 Correct 65 ms 191316 KB ok
47 Correct 129 ms 267088 KB ok
48 Correct 129 ms 267980 KB ok
49 Correct 121 ms 264788 KB ok
50 Correct 122 ms 264208 KB ok
51 Correct 131 ms 266068 KB ok
52 Correct 104 ms 263724 KB ok
53 Correct 124 ms 261968 KB ok
54 Correct 106 ms 261716 KB ok
55 Correct 108 ms 263760 KB ok
56 Correct 118 ms 264784 KB ok
57 Correct 106 ms 256936 KB ok
58 Correct 109 ms 254452 KB ok
59 Correct 111 ms 257108 KB ok
60 Correct 112 ms 260048 KB ok
61 Correct 107 ms 257348 KB ok
62 Correct 121 ms 267856 KB ok
63 Correct 119 ms 268428 KB ok
64 Correct 120 ms 268984 KB ok
65 Correct 1283 ms 728396 KB ok
66 Correct 891 ms 731888 KB ok
67 Correct 601 ms 701612 KB ok
68 Correct 628 ms 678148 KB ok
69 Correct 807 ms 690092 KB ok
70 Correct 943 ms 699932 KB ok
71 Correct 581 ms 677204 KB ok
72 Correct 486 ms 675668 KB ok
73 Correct 557 ms 668240 KB ok
74 Correct 570 ms 668532 KB ok
75 Correct 585 ms 668752 KB ok
76 Correct 510 ms 675816 KB ok
77 Correct 518 ms 676012 KB ok
78 Correct 724 ms 686616 KB ok
79 Correct 538 ms 680480 KB ok
80 Correct 506 ms 678860 KB ok
81 Correct 519 ms 679008 KB ok
82 Correct 578 ms 682668 KB ok
83 Correct 669 ms 696080 KB ok
84 Correct 791 ms 629648 KB ok
85 Correct 481 ms 623172 KB ok
86 Correct 827 ms 634260 KB ok
87 Execution timed out 4565 ms 637496 KB Time limit exceeded
88 Halted 0 ms 0 KB -