oj.uz

답안 #1017136

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017136 2024-07-08T22:16:32 Z MilosMilutinovic 축구 경기장 (IOI23_soccer) C++17
70 / 100
 4500 ms 732904 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;
        }
        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 74 ms 189520 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 189268 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 64 ms 189776 KB ok
4 Correct 66 ms 189816 KB ok
5 Correct 68 ms 189264 KB ok
6 Correct 68 ms 189264 KB ok
7 Correct 82 ms 198480 KB ok
8 Correct 102 ms 263660 KB ok
9 Correct 557 ms 675812 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 189268 KB ok
2 Correct 67 ms 189264 KB ok
3 Correct 68 ms 189264 KB ok
4 Correct 70 ms 189268 KB ok
5 Correct 66 ms 189272 KB ok
6 Correct 68 ms 189264 KB ok
7 Correct 65 ms 189264 KB ok
8 Correct 66 ms 189172 KB ok
9 Correct 66 ms 189264 KB ok
10 Correct 66 ms 189164 KB ok
11 Correct 73 ms 189520 KB ok
12 Correct 65 ms 189268 KB ok
13 Correct 67 ms 189236 KB ok

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 189520 KB ok
2 Correct 65 ms 189268 KB ok
3 Correct 67 ms 189264 KB ok
4 Correct 68 ms 189264 KB ok
5 Correct 70 ms 189268 KB ok
6 Correct 66 ms 189272 KB ok
7 Correct 68 ms 189264 KB ok
8 Correct 65 ms 189264 KB ok
9 Correct 66 ms 189172 KB ok
10 Correct 66 ms 189264 KB ok
11 Correct 66 ms 189164 KB ok
12 Correct 73 ms 189520 KB ok
13 Correct 65 ms 189268 KB ok
14 Correct 67 ms 189236 KB ok
15 Correct 65 ms 189516 KB ok
16 Correct 66 ms 189516 KB ok
17 Correct 68 ms 189608 KB ok
18 Correct 65 ms 189520 KB ok
19 Correct 66 ms 189520 KB ok
20 Correct 67 ms 189420 KB ok
21 Correct 67 ms 189496 KB ok
22 Correct 66 ms 189520 KB ok
23 Correct 66 ms 189524 KB ok
24 Correct 67 ms 189476 KB ok
25 Correct 66 ms 189488 KB ok
26 Correct 81 ms 189524 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 189520 KB ok
2 Correct 65 ms 189268 KB ok
3 Correct 67 ms 189264 KB ok
4 Correct 64 ms 189776 KB ok
5 Correct 66 ms 189816 KB ok
6 Correct 68 ms 189264 KB ok
7 Correct 70 ms 189268 KB ok
8 Correct 66 ms 189272 KB ok
9 Correct 68 ms 189264 KB ok
10 Correct 65 ms 189264 KB ok
11 Correct 66 ms 189172 KB ok
12 Correct 66 ms 189264 KB ok
13 Correct 66 ms 189164 KB ok
14 Correct 73 ms 189520 KB ok
15 Correct 65 ms 189268 KB ok
16 Correct 67 ms 189236 KB ok
17 Correct 65 ms 189516 KB ok
18 Correct 66 ms 189516 KB ok
19 Correct 68 ms 189608 KB ok
20 Correct 65 ms 189520 KB ok
21 Correct 66 ms 189520 KB ok
22 Correct 67 ms 189420 KB ok
23 Correct 67 ms 189496 KB ok
24 Correct 66 ms 189520 KB ok
25 Correct 66 ms 189524 KB ok
26 Correct 67 ms 189476 KB ok
27 Correct 66 ms 189488 KB ok
28 Correct 81 ms 189524 KB ok
29 Correct 69 ms 189452 KB ok
30 Correct 67 ms 191312 KB ok
31 Correct 68 ms 191316 KB ok
32 Correct 68 ms 191316 KB ok
33 Correct 73 ms 191312 KB ok
34 Correct 65 ms 191316 KB ok
35 Correct 69 ms 191232 KB ok
36 Correct 68 ms 191056 KB ok
37 Correct 70 ms 191060 KB ok
38 Correct 67 ms 191048 KB ok
39 Correct 67 ms 191060 KB ok
40 Correct 66 ms 191152 KB ok
41 Correct 71 ms 191316 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 189520 KB ok
2 Correct 65 ms 189268 KB ok
3 Correct 67 ms 189264 KB ok
4 Correct 64 ms 189776 KB ok
5 Correct 66 ms 189816 KB ok
6 Correct 68 ms 189264 KB ok
7 Correct 70 ms 189268 KB ok
8 Correct 66 ms 189272 KB ok
9 Correct 68 ms 189264 KB ok
10 Correct 65 ms 189264 KB ok
11 Correct 66 ms 189172 KB ok
12 Correct 66 ms 189264 KB ok
13 Correct 66 ms 189164 KB ok
14 Correct 73 ms 189520 KB ok
15 Correct 65 ms 189268 KB ok
16 Correct 67 ms 189236 KB ok
17 Correct 65 ms 189516 KB ok
18 Correct 66 ms 189516 KB ok
19 Correct 68 ms 189608 KB ok
20 Correct 65 ms 189520 KB ok
21 Correct 66 ms 189520 KB ok
22 Correct 67 ms 189420 KB ok
23 Correct 67 ms 189496 KB ok
24 Correct 66 ms 189520 KB ok
25 Correct 66 ms 189524 KB ok
26 Correct 67 ms 189476 KB ok
27 Correct 66 ms 189488 KB ok
28 Correct 81 ms 189524 KB ok
29 Correct 69 ms 189452 KB ok
30 Correct 67 ms 191312 KB ok
31 Correct 68 ms 191316 KB ok
32 Correct 68 ms 191316 KB ok
33 Correct 73 ms 191312 KB ok
34 Correct 65 ms 191316 KB ok
35 Correct 69 ms 191232 KB ok
36 Correct 68 ms 191056 KB ok
37 Correct 70 ms 191060 KB ok
38 Correct 67 ms 191048 KB ok
39 Correct 67 ms 191060 KB ok
40 Correct 66 ms 191152 KB ok
41 Correct 71 ms 191316 KB ok
42 Correct 136 ms 267212 KB ok
43 Correct 138 ms 267976 KB ok
44 Correct 121 ms 264652 KB ok
45 Correct 113 ms 264392 KB ok
46 Correct 123 ms 266160 KB ok
47 Correct 103 ms 263828 KB ok
48 Correct 107 ms 261712 KB ok
49 Correct 110 ms 261596 KB ok
50 Correct 109 ms 263764 KB ok
51 Correct 108 ms 265084 KB ok
52 Correct 120 ms 256852 KB ok
53 Correct 104 ms 254292 KB ok
54 Correct 114 ms 257300 KB ok
55 Correct 116 ms 259920 KB ok
56 Correct 104 ms 257340 KB ok
57 Correct 113 ms 267796 KB ok
58 Correct 117 ms 268368 KB ok
59 Correct 134 ms 268880 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 189520 KB ok
2 Correct 65 ms 189268 KB ok
3 Correct 67 ms 189264 KB ok
4 Correct 64 ms 189776 KB ok
5 Correct 66 ms 189816 KB ok
6 Correct 68 ms 189264 KB ok
7 Correct 68 ms 189264 KB ok
8 Correct 82 ms 198480 KB ok
9 Correct 102 ms 263660 KB ok
10 Correct 557 ms 675812 KB ok
11 Correct 68 ms 189264 KB ok
12 Correct 70 ms 189268 KB ok
13 Correct 66 ms 189272 KB ok
14 Correct 68 ms 189264 KB ok
15 Correct 65 ms 189264 KB ok
16 Correct 66 ms 189172 KB ok
17 Correct 66 ms 189264 KB ok
18 Correct 66 ms 189164 KB ok
19 Correct 73 ms 189520 KB ok
20 Correct 65 ms 189268 KB ok
21 Correct 67 ms 189236 KB ok
22 Correct 65 ms 189516 KB ok
23 Correct 66 ms 189516 KB ok
24 Correct 68 ms 189608 KB ok
25 Correct 65 ms 189520 KB ok
26 Correct 66 ms 189520 KB ok
27 Correct 67 ms 189420 KB ok
28 Correct 67 ms 189496 KB ok
29 Correct 66 ms 189520 KB ok
30 Correct 66 ms 189524 KB ok
31 Correct 67 ms 189476 KB ok
32 Correct 66 ms 189488 KB ok
33 Correct 81 ms 189524 KB ok
34 Correct 69 ms 189452 KB ok
35 Correct 67 ms 191312 KB ok
36 Correct 68 ms 191316 KB ok
37 Correct 68 ms 191316 KB ok
38 Correct 73 ms 191312 KB ok
39 Correct 65 ms 191316 KB ok
40 Correct 69 ms 191232 KB ok
41 Correct 68 ms 191056 KB ok
42 Correct 70 ms 191060 KB ok
43 Correct 67 ms 191048 KB ok
44 Correct 67 ms 191060 KB ok
45 Correct 66 ms 191152 KB ok
46 Correct 71 ms 191316 KB ok
47 Correct 136 ms 267212 KB ok
48 Correct 138 ms 267976 KB ok
49 Correct 121 ms 264652 KB ok
50 Correct 113 ms 264392 KB ok
51 Correct 123 ms 266160 KB ok
52 Correct 103 ms 263828 KB ok
53 Correct 107 ms 261712 KB ok
54 Correct 110 ms 261596 KB ok
55 Correct 109 ms 263764 KB ok
56 Correct 108 ms 265084 KB ok
57 Correct 120 ms 256852 KB ok
58 Correct 104 ms 254292 KB ok
59 Correct 114 ms 257300 KB ok
60 Correct 116 ms 259920 KB ok
61 Correct 104 ms 257340 KB ok
62 Correct 113 ms 267796 KB ok
63 Correct 117 ms 268368 KB ok
64 Correct 134 ms 268880 KB ok
65 Correct 1072 ms 729336 KB ok
66 Correct 823 ms 732904 KB ok
67 Correct 590 ms 701864 KB ok
68 Correct 631 ms 678160 KB ok
69 Correct 771 ms 690140 KB ok
70 Correct 883 ms 700104 KB ok
71 Correct 597 ms 677200 KB ok
72 Correct 514 ms 675668 KB ok
73 Correct 568 ms 668188 KB ok
74 Correct 579 ms 668344 KB ok
75 Correct 624 ms 668756 KB ok
76 Correct 544 ms 675964 KB ok
77 Correct 547 ms 675848 KB ok
78 Correct 778 ms 687600 KB ok
79 Correct 525 ms 680644 KB ok
80 Correct 513 ms 679012 KB ok
81 Correct 521 ms 679112 KB ok
82 Correct 603 ms 682952 KB ok
83 Correct 664 ms 697272 KB ok
84 Correct 738 ms 629668 KB ok
85 Correct 468 ms 623228 KB ok
86 Correct 813 ms 634192 KB ok
87 Execution timed out 4573 ms 637184 KB Time limit exceeded
88 Halted 0 ms 0 KB -