Submission #1195636

#TimeUsernameProblemLanguageResultExecution timeMemory
1195636mannshah1211Soccer Stadium (IOI23_soccer)C++20
48 / 100
2051 ms2162688 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...