Submission #1072514

#TimeUsernameProblemLanguageResultExecution timeMemory
1072514HorizonWestSoccer Stadium (IOI23_soccer)C++17
30 / 100
6 ms8796 KiB
#include "soccer.h" #include <iostream> #include <complex> #include <iomanip> #include <vector> #include <algorithm> #include <functional> #include <bitset> #include <queue> #include <map> #include <stack> #include <cmath> #include <cstdint> #include <cassert> using namespace std; int biggest_stadium(int n, std::vector<std::vector<int>> f) { vector <vector<int>> A(n, vector <int> (n, 0)), B(n, vector <int> (n, 0)); for(int i = 0; i < n; i++){ int last = -1; for(int j = 0; j < n; j++){ if(f[i][j] == 1) last = j; A[i][j] = last; } last = n; for(int j = n-1; j >= 0; j--){ if(f[i][j] == 1) last = j; B[i][j] = last; } } //vector <vector<vector<int>>> dp1(n + 1, vector <vector<int>> // (n + 1, vector <int> (n + 1, -1))); //vector <vector<vector<int>>> dp2(n + 1, vector <vector<int>> // (n + 1, vector <int> (n + 1, -1))); int dp[10][10][10][10][10][10] = { }; auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int { if(dp[i][j][a][b][c][d] != 0) return dp[i][j][a][b][c][d]; dp[i][j][a][b][c][d] = (b - a + 1); if(i != j) dp[i][j][a][b][c][d] += (d - c + 1); int mx = 0; if(i != 0) { for(int k = a; k <= b; k++) if(f[i-1][k] == 0) { int l1 = max(A[i-1][k]+1, a), r1 = min(B[i-1][k]-1, b); int l2 = max(c, l1), r2 = min(d, r1); mx = max(mx, F(F, i-1, j, l1, r1, l2, r2) - (r2 - l2 + 1)); } } if(j != n-1) { for(int k = c; k <= d; k++) if(f[j+1][k] == 0) { int l2 = max(A[j+1][k]+1, c), r2 = min(B[j+1][k]-1, d); int l1 = max(a, l2), r1 = min(b, r2); mx = max(mx, F(F, i, j+1, l1, r1, l2, r2) - (r1 - l1 + 1)); } } return dp[i][j][a][b][c][d] = (dp[i][j][a][b][c][d] + mx); }; int ans = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { int l = A[i][j]+1, r = B[i][j]-1; ans = max(ans, F(F, i, i, l, r, l, r)); } } return ans; }
#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...