Submission #840724

#TimeUsernameProblemLanguageResultExecution timeMemory
840724danikoynovSoccer Stadium (IOI23_soccer)C++17
54 / 100
4530 ms509860 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2010; int a[maxn][maxn], bef[maxn][maxn], aft[maxn][maxn]; int dp[510][510][510], pref[maxn][maxn]; int biggest_stadium(int N, std::vector<std::vector<int>> F) { int cnt = 0; int x1 = 0, y1 = 0; for (int i = 0; i < N; i ++) for (int j = 0; j < N; j ++) { cnt += F[i][j]; if (F[i][j] == 1) x1 = i + 1, y1 = j + 1; a[i + 1][j + 1] = F[i][j]; } if (cnt == 1) { int ans = N * N - min(x1, N - x1 + 1) * min(y1, N - y1 + 1); return ans; } for (int j = 1; j <= N; j ++) { for (int i = 1; i <= N; i ++) pref[i][j] = pref[i - 1][j] + a[i][j]; } for (int i = 1; i <= N; i ++) { for (int j = 1; j <= N; j ++) { if (a[i][j] == 1) bef[i][j] = j; else bef[i][j] = bef[i][j - 1]; } aft[i][N + 1] = N + 1; for (int j = N; j > 0; j --) { if (a[i][j] == 1) aft[i][j] = j; else aft[i][j] = aft[i][j + 1]; } } int ans = 0; for (int col = 1; col <= N; col ++) ///int col = 5; { for (int len = 1; len <= N; len ++) { for (int i = 1; i <= N - len + 1; i ++) { int j = i + len - 1; if (pref[j][col] - pref[i - 1][col] > 0) continue; if (col != 1 && pref[j][col - 1] - pref[i - 1][col - 1] == 0) { dp[col][i][j] = dp[col - 1][i][j]; continue; } int left_width = N, right_width = N; for (int k = i; k <= j; k ++) { left_width = min(left_width, col - bef[k][col]); right_width = min(right_width, aft[k][col] - col); } int base_area = (j - i + 1) * (left_width + right_width - 1); dp[col][i][j] = base_area; if (left_width != col) { vector < int > split; split.push_back(i - 1); for (int k = i; k <= j; k ++) { if (bef[k][col] == col - left_width) split.push_back(k); } split.push_back(j + 1); for (int d = 1; d < (int)(split.size()); d ++) { ///cout << "check " << split[d - 1] + 1 << " " << split[d] - 1 << endl; int rem_area = (split[d] - split[d - 1] - 1) * (left_width + right_width - 1); dp[col][i][j] = max(dp[col][i][j], dp[col][split[d - 1] + 1][split[d] - 1] - rem_area + base_area); } } if (right_width != N + 1 - col) { vector < int > split; split.push_back(i - 1); for (int k = i; k <= j; k ++) { if (aft[k][col] == col + right_width) split.push_back(k); } split.push_back(j + 1); for (int d = 1; d < (int)(split.size()); d ++) { int rem_area = (split[d] - split[d - 1] - 1) * (left_width + right_width - 1); dp[col][i][j] = max(dp[col][i][j], dp[col][split[d - 1] + 1][split[d] - 1] - rem_area + base_area); } } ans = max(ans, dp[col][i][j]); ///cout << i << " : " << j << " = " << dp[col][i][j] << endl; } } } 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...