제출 #1195617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195617		mannshah1211	축구 경기장 (IOI23_soccer)	C++20	30 / 100	4595 ms	2162688 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int inf = int(1e9);

int biggest_stadium(int n, vector<vector<int>> f) {
  vector can(n, vector(n, vector<bool>(n)));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      bool ok = true;
      for (int k = j; k < n; k++) {
        if (!f[i][k]) {
          can[i][j][k] = true;
        } else {
          break;
        }
      }
    }
  }
  int mx = 0;
  for (int pivot = 0; pivot < n; pivot++) {
    vector dp(n, vector(n, vector(n, vector(n, vector<int>(2, -inf)))));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = j; k < n; k++) {
          if (i == pivot) {
            if (can[i][j][k]) {
              dp[i][i][j][k][0] = k - j + 1;
              dp[i][i][j][k][1] = k - j + 1;
              mx = max(mx, dp[i][i][j][k][0]);
            }
          }
        }
      } 
    }
    for (int len = 2; len <= n; len++) {
      for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        for (int k = 0; k < n; k++) {
          for (int l = k; l < n; l++) {
            for (int e = 0; e < n; e++) {
              for (int f = e; f < n; f++) {
                if (k >= e && l <= f) {
                  if (can[i][k][l] && can[j][e][f]) {
                    dp[i][j][k][l][0] = max(dp[i + 1][j][e][f][1] + (l - k + 1), dp[i][j][k][l][0]);
                    mx = max(mx, dp[i][j][k][l][0]);
                  }
                  if (can[i][k][l] && can[i + 1][e][f]) {
                    dp[i][j][k][l][0] = max(dp[i + 1][j][e][f][0] + (l - k + 1), dp[i][j][k][l][0]);
                    mx = max(mx, dp[i][j][k][l][0]);
                  }
                  if (can[j][k][l] && can[i][e][f]) {
                    dp[i][j][k][l][1] = max(dp[i][j - 1][e][f][0] + (l - k + 1), dp[i][j][k][l][1]);
                    mx = max(mx, dp[i][j][k][l][1]);
                  }
                  if (can[j][k][l] && can[j - 1][e][f]) {
                    dp[i][j][k][l][1] = max(dp[i][j - 1][e][f][1] + (l - k + 1), dp[i][j][k][l][1]);
                    mx = max(mx, dp[i][j][k][l][1]);
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  return mx;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30