oj.uz

답안 #900229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
900229 2024-01-07T23:12:39 Z MilosMilutinovic 축구 경기장 (IOI23_soccer) C++17
48 / 100
 1840 ms 93128 KB 
//#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int inf = (int) 1e9;

const int N = 52;

int dp[N][N][N][N];

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

bool check_all(int n, vector<vector<int>> a) {
  vector<vector<bool>> was(n, vector<bool>(n));
  function<void(int, int)> Dfs = [&](int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= n || a[x][y] == 1 || was[x][y]) {
      return;
    }
    was[x][y] = true;
    for (int d = 0; d < 4; d++) {
      Dfs(x + dx[d], y + dy[d]);
    }
  };
  bool done = false;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!done && a[i][j] == 0) {
        Dfs(i, j);
        done = true;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (a[i][j] == 0 && !was[i][j]) {
        return false;
      }
    }
  }
  vector<pair<int, int>> seg;
  for (int j = 0; j < n; j++) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 1) {
        continue;
      }
      cnt += 1;
      if (cnt == 2) {
        return false;
      }
      int ptr = i;
      while (ptr + 1 < n && a[ptr + 1][j] == 0) {
        ptr += 1;
      }
      seg.emplace_back(i, ptr);
      i = ptr;
    }
  }
  int sz = (int) seg.size();
  int mx = 0;
  for (int i = 1; i < sz; i++) {
    if (seg[i].second - seg[i].first > seg[mx].second - seg[mx].first) {
      mx = i;
    }
  }
  int l = mx, r = mx, lst = mx;
  while (l != 0 || r != sz - 1) {
    if (l == 0 || (r + 1 < sz && seg[r + 1].second - seg[r + 1].first > seg[l - 1].second - seg[l - 1].first)) {
      if (!(seg[lst].first <= seg[r + 1].first && seg[r + 1].second <= seg[lst].second)) {
        return false;
      }
      r += 1;
      lst = r;
    } else {
      if (!(seg[lst].first <= seg[l - 1].first && seg[l - 1].second <= seg[lst].second)) {
        return false;
      }
      l -= 1;
      lst = l;
    }
  }
  return true;
}

int biggest_stadium(int n, vector<vector<int>> a) {
  if (check_all(n, a)) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (a[i][j] == 0) {
          cnt += 1;
        }
      }
    }
    return cnt;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
          dp[i][j][x][y] = -inf;
        }
      }
    }
  }
  for (int r = 0; r < n; r++) {
    for (int l = r; l >= 0; l--) {
      if (l == r) {
        for (int i = 0; i < n; i++) {
          int cnt = 0;
          for (int j = i; j < n; j++) {
            cnt += 1;
            if (a[l][j] == 1) {
              break;
            }
            dp[l][r][i][j] = cnt;
          }
        }
        continue;
      }
      {
        // left
        for (int i = 0; i < n; i++) {
          for (int j = i; j < n; j++) {
            if (a[l][j] == 1) {
              break;
            }
            for (int x = 0; x <= i; x++) {
              for (int y = j; y < n; y++) {
                dp[l][r][i][j] = max(dp[l][r][i][j], dp[l + 1][r][x][y] + (j - i + 1));
              }
            }
          }
        }
      }
      {
        // right
        for (int i = 0; i < n; i++) {
          for (int j = i; j < n; j++) {
            if (a[r][j] == 1) {
              break;
            }
            for (int x = 0; x <= i; x++) {
              for (int y = j; y < n; y++) {
                dp[l][r][i][j] = max(dp[l][r][i][j], dp[l][r - 1][x][y] + (j - i + 1));
              }
            }
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
          res = max(res, dp[i][j][x][y]);
        }
      }
    }
  }
  return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 344 KB ok
6 Correct 1 ms 2392 KB ok
7 Runtime error 49 ms 60192 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 2396 KB ok
5 Correct 0 ms 2396 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 1 ms 2396 KB ok
12 Correct 0 ms 2396 KB ok
13 Correct 0 ms 2396 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 4440 KB ok
16 Correct 1 ms 4444 KB ok
17 Correct 1 ms 4444 KB ok
18 Correct 1 ms 4444 KB ok
19 Correct 1 ms 4444 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 4696 KB ok
23 Correct 1 ms 4444 KB ok
24 Correct 1 ms 4444 KB ok
25 Correct 1 ms 4444 KB ok
26 Correct 1 ms 4444 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 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 1 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 0 ms 2396 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 4440 KB ok
18 Correct 1 ms 4444 KB ok
19 Correct 1 ms 4444 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 4696 KB ok
25 Correct 1 ms 4444 KB ok
26 Correct 1 ms 4444 KB ok
27 Correct 1 ms 4444 KB ok
28 Correct 1 ms 4444 KB ok
29 Correct 1 ms 4444 KB ok
30 Correct 22 ms 17076 KB ok
31 Correct 19 ms 17064 KB ok
32 Correct 7 ms 16988 KB ok
33 Correct 4 ms 16988 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 5 ms 17028 KB ok
37 Correct 8 ms 17028 KB ok
38 Correct 7 ms 16988 KB ok
39 Correct 9 ms 16984 KB ok
40 Correct 26 ms 16984 KB ok
41 Correct 32 ms 16988 KB ok

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 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 1 ms 2396 KB ok
7 Correct 0 ms 2396 KB ok
8 Correct 1 ms 2396 KB ok
9 Correct 0 ms 2396 KB ok
10 Correct 1 ms 2396 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 1 ms 2396 KB ok
14 Correct 0 ms 2396 KB ok
15 Correct 0 ms 2396 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 4440 KB ok
18 Correct 1 ms 4444 KB ok
19 Correct 1 ms 4444 KB ok
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 4696 KB ok
25 Correct 1 ms 4444 KB ok
26 Correct 1 ms 4444 KB ok
27 Correct 1 ms 4444 KB ok
28 Correct 1 ms 4444 KB ok
29 Correct 1 ms 4444 KB ok
30 Correct 22 ms 17076 KB ok
31 Correct 19 ms 17064 KB ok
32 Correct 7 ms 16988 KB ok
33 Correct 4 ms 16988 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 5 ms 17028 KB ok
37 Correct 8 ms 17028 KB ok
38 Correct 7 ms 16988 KB ok
39 Correct 9 ms 16984 KB ok
40 Correct 26 ms 16984 KB ok
41 Correct 32 ms 16988 KB ok
42 Runtime error 1840 ms 93128 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 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 344 KB ok
7 Correct 1 ms 2392 KB ok
8 Runtime error 49 ms 60192 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -