Submission #1195636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195636		mannshah1211	축구 경기장 (IOI23_soccer)	C++20	48 / 100	2051 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)))));
    vector pre(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 i = 0; i < n; i++) {
      for (int len = n; len >= 1; len--) {
        for (int j = 0; j <= n - len; j++) {
          int k = j + len - 1;
          pre[i][i][j][k][0] = dp[i][i][j][k][0];
          pre[i][i][j][k][1] = dp[i][i][j][k][1];
          if (j - 1 >= 0) {
            pre[i][i][j][k][0] = max({pre[i][i][j][k][0], dp[i][i][j][k][0], pre[i][i][j - 1][k][0]});
            pre[i][i][j][k][1] = max({pre[i][i][j][k][1], dp[i][i][j][k][1], pre[i][i][j - 1][k][1]});
          }
          if (k + 1 < n) {
            pre[i][i][j][k][0] = max({pre[i][i][j][k][0], dp[i][i][j][k][0], pre[i][i][j][k + 1][0]});
            pre[i][i][j][k][1] = max({pre[i][i][j][k][1], dp[i][i][j][k][1], pre[i][i][j][k + 1][1]});
          }
        }
      }
    }
    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++) {
            if (can[i][k][l]) {
              dp[i][j][k][l][0] = max(dp[i][j][k][l][0], pre[i + 1][j][k][l][1] + (l - k + 1));
              dp[i][j][k][l][0] = max(dp[i][j][k][l][0], pre[i + 1][j][k][l][0] + (l - k + 1));
              mx = max(mx, dp[i][j][k][l][0]);
            }
            if (can[j][k][l]) {
              dp[i][j][k][l][1] = max(dp[i][j][k][l][1], pre[i][j - 1][k][l][1] + (l - k + 1));
              dp[i][j][k][l][1] = max(dp[i][j][k][l][1], pre[i][j - 1][k][l][0] + (l - k + 1));
              mx = max(mx, dp[i][j][k][l][1]);
            }
          }
        }
        for (int len2 = n; len2 >= 1; len2--) {
          for (int k = 0; k <= n - len2; k++) {
            int l = k + len2 - 1;
            pre[i][j][k][l][0] = dp[i][j][k][l][0];
            pre[i][j][k][l][1] = dp[i][j][k][l][1];
            if (k - 1 >= 0) {
              pre[i][j][k][l][0] = max({pre[i][j][k][l][0], dp[i][j][k][l][0], pre[i][j][k - 1][l][0]});
              pre[i][j][k][l][1] = max({pre[i][j][k][l][1], dp[i][j][k][l][1], pre[i][j][k - 1][l][1]});
            }
            if (l + 1 < n) {
              pre[i][j][k][l][0] = max({pre[i][j][k][l][0], dp[i][j][k][l][0], pre[i][j][k][l + 1][0]});
              pre[i][j][k][l][1] = max({pre[i][j][k][l][1], dp[i][j][k][l][1], pre[i][j][k][l + 1][1]});
            }
          }
        }
      }
    }
  }
  return mx;
}

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