Submission #844638

#TimeUsernameProblemLanguageResultExecution timeMemory
844638SortingSoccer Stadium (IOI23_soccer)C++17
0 / 100
5 ms1116 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; const int N = 7; bool f[N][N]; int prefix[N][N]; int n; pair<int, bool> dp[N][N][N][N][N][N]; bool bad(int l1, int r1, int l2, int r2){ if(l1 <= l2 && r2 <= r1) return false; if(l2 <= l1 && r1 <= r2) return false; return true; } int solve(int i1, int i2, int l1, int r1, int l2, int r2){ auto &[ans, solved] = dp[i1][i2][l1][r1][l2][r2]; if(solved) return ans; solved = true; ans = 0; if(r1 - l1 >= r2 - l2 && i1 != 0){ for(int l3 = 0; l3 < n; ++l3){ for(int r3 = l3; r3 < n; ++r3){ if(f[i1 - 1][r3]) break; if(bad(l3, r3, l1, r1)) continue; if(bad(l3, r3, l2, r2)) continue; if(r3 - l3 > r1 - l1) continue; ans = max(ans, solve(i1 - 1, i2, l3, r3, l2, r2) + r3 - l3 + 1); } } } if(r2 - l2 >= r1 - l1 && i2 != n - 1){ for(int l3 = 0; l3 < n; ++l3){ for(int r3 = l3; r3 < n; ++r3){ if(f[i2 + 1][r3]) break; if(bad(l3, r3, l1, r1)) continue; if(bad(l3, r3, l2, r2)) continue; if(r3 - l3 > r2 - l2) continue; ans = max(ans, solve(i1, i2 + 1, l1, r1, l3, r3) + r3 - l3 + 1); } } } return ans; } int biggest_stadium(int _N, std::vector<std::vector<int>> F){ n = _N; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) f[i][j] = F[i][j]; int ans = 0; for(int i = 0; i < n; ++i){ for(int l = 0; l < n; ++l){ for(int r = l; r < n; ++r){ if(f[i][r]) break; ans = max(ans, solve(i, i, l, r, l, r) + r - l + 1); } } } return ans; } /* 3 1 1 1 1 1 1 1 1 1 */
#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...