oj.uz

답안 #1038091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038091 2024-07-29T12:53:53 Z erray 축구 경기장 (IOI23_soccer) C++17
6 / 100
 193 ms 31788 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/egoi2024/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

constexpr int mx_N = 30;
int dp[mx_N][mx_N][mx_N][mx_N];
void ckmax(int& x, int y) {
  x = max(x, y);
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
  int tree_count = 0, one_tree_i, one_tree_j;
  for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
    if (F[i][j]) {
      tree_count++;
      one_tree_i = i, one_tree_j = j;
    }
  }
  if (tree_count <= 1) {
    if (tree_count == 0) return N * N;
    int i = one_tree_i;
    int j = one_tree_j;
    return N * N - min(i + 1, N - i) * min(j + 1, N - j);
  }
  if (N > mx_N) {
    vector<int> T(N, -1), B(N, -1), L(N, -1), R(N, -1);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (F[i][j]) continue;
        if (T[j] == -1) T[j] = N - 1 - i;
        if (L[i] == -1) L[i] = N - 1 - j;
        B[j] = i;
        R[i] = j;
      }
    }
    int verc = 0, horc = 0;
    for (int i = 0; i < N; ++i) {
      if (L[i] != -1) {
        horc += 2 * (N - 1) - (L[i] + R[i]);
      } else {
        horc += N;
      }
      if (T[i] != -1) {
        verc += 2 * (N - 1) - (T[i] + B[i]);
      } else {
        verc += N;
      }
    }
    bool bad = (verc != tree_count || horc != tree_count);
    if (bad) {
      return 0;
    }
    debug(bad, L, R, B, T);
    int max_L = *max_element(L.begin(), L.end());
    int max_R = *max_element(R.begin(), R.end());
    int max_B = *max_element(B.begin(), B.end());
    int max_T = *max_element(T.begin(), T.end());
    int mx_H = -1;
    for (int i = 0; i < N; ++i) {
      if (L[i] == max_L && R[i] == max_R) mx_H = i;
    }
    if (mx_H == -1) bad = true;
    else {
      for (int i = 0; i < mx_H; ++i) {
        if (L[i] == -1) continue;
        if (L[i + 1] == -1 || L[i + 1] < L[i] || R[i + 1] < R[i]) bad = true;
      }    
      for (int i = mx_H + 1; i < N; ++i) {
        if (L[i] == -1) continue;
        if (L[i - 1] == -1 || L[i - 1] < L[i] || R[i - 1] < R[i]) bad = true;
      }
    } 
    vector<array<int, 2>> ranges;
    for (int i = 0; i < N; ++i) {
      if (L[i] != -1) ranges.push_back({L[i], R[i]});
    }
    sort(ranges.begin(), ranges.end());
    for (int i = 0; i < int(ranges.size()) - 1; ++i) {
      if (ranges[i + 1][1] < ranges[i][1]) bad = true;
    }
    if (bad) {
      return 0;
    } else {
      return N * N - tree_count;
    }
  }
  int mx = 0;
  for (int u = N - 1; u >= 0; --u) {
    for (int d = u; d < N; ++d) {
      for (int l = 0; l < N; ++l) {
        for (int r = l; r < N; ++r) {
          if (u == d) {
            int c = 0;
            for (int j = l; j <= r; ++j) c += F[u][j];
            if (c == 0) dp[u][d][l][r] = r - l + 1;
          }    
          debug(u, d, l, r, dp[u][d][l][r]);          
          mx = max(mx, dp[u][d][l][r]);
          if (u > 0) {
            int block = N - 1;
            for (int nl = N - 1; nl >= l; --nl) {
              if (F[u - 1][nl]) {
                block = nl - 1;
                continue;
              }
              int nr = min(r, block);
              ckmax(dp[u - 1][d][nl][nr], dp[u][d][l][r] + nr - nl + 1);
            }
          }
          if (d < N - 1) {
            int block = N - 1;
            for (int nl = N - 1; nl >= l; --nl) {
              if (F[d + 1][nl]) {
                block = nl - 1;
                continue;
              }
              int nr = min(r, block);
              ckmax(dp[u][d + 1][nl][nr], dp[u][d][l][r] + nr - nl + 1);
            }
          }
        }
      }
    }
  }
  return mx;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:63:9: warning: unused variable 'max_B' [-Wunused-variable]
   63 |     int max_B = *max_element(B.begin(), B.end());
      |         ^~~~~
soccer.cpp:64:9: warning: unused variable 'max_T' [-Wunused-variable]
   64 |     int max_T = *max_element(T.begin(), T.end());
      |         ^~~~~
soccer.cpp:30:46: warning: 'one_tree_j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     return N * N - min(i + 1, N - i) * min(j + 1, N - j);
      |                                            ~~^~~
soccer.cpp:30:26: warning: 'one_tree_i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     return N * N - min(i + 1, N - i) * min(j + 1, N - j);
      |                        ~~^~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 12 ms 2396 KB ok
9 Correct 193 ms 31788 KB ok

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 2392 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 2396 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 2396 KB ok
11 Incorrect 1 ms 2396 KB wrong
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 2392 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 2396 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 2396 KB ok
12 Incorrect 1 ms 2396 KB wrong
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 2396 KB ok
14 Incorrect 1 ms 2396 KB wrong
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 2392 KB ok
7 Correct 1 ms 2396 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 2396 KB ok
14 Incorrect 1 ms 2396 KB wrong
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB ok
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 12 ms 2396 KB ok
10 Correct 193 ms 31788 KB ok
11 Correct 1 ms 2392 KB ok
12 Correct 1 ms 2396 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 2396 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 1 ms 2396 KB ok
19 Incorrect 1 ms 2396 KB wrong
20 Halted 0 ms 0 KB -