Submission #964435

#TimeUsernameProblemLanguageResultExecution timeMemory
964435nguyentunglamSoccer Stadium (IOI23_soccer)C++17
100 / 100
2069 ms415888 KiB
#include "soccer.h" #include<bits/stdc++.h> #define all(v) v.begin(), v.end() using namespace std; const int N = 2010; int n; bool a[N][N]; namespace AC { const int N = 2010, M = 2e3 * 2e3 * 2 + 10; int b[N], L[N], R[N], dp[M], trans[2][M]; int close[N]; vector<int> open[N], lst[N], event[2][N]; tuple<int, int, int, int> rect[M]; int solve() { int m = 0; auto histogram = [&] () { stack<int> st; for(int i = 1; i <= n; i++) { while (!st.empty() && b[st.top()] >= b[i]) st.pop(); L[i] = st.empty() ? 0 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for(int i = n; i >= 1; i--) { while (!st.empty() && b[st.top()] >= b[i]) st.pop(); R[i] = st.empty() ? n + 1 : st.top(); st.push(i); } }; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if (a[i][j]) b[j] = 0; else b[j]++; } histogram(); for(int j = 1; j <= n; j++) if (b[j]) { rect[++m] = make_tuple(i - b[j] + 1, i, L[j] + 1, R[j] - 1); } } for(int j = 1; j <= n; j++) b[j] = 0; for(int i = n; i >= 1; i--) { for(int j = 1; j <= n; j++) { if (a[i][j]) b[j] = 0; else b[j]++; } histogram(); for(int j = 1; j <= n; j++) if (b[j]) { rect[++m] = make_tuple(i, i + b[j] - 1, L[j] + 1, R[j] - 1); } } for(int i = 1; i <= m; i++) { lst[get<1> (rect[i]) - get<0> (rect[i])].push_back(i); } for(int delta = 0; delta < n; delta++) { for(int &i : lst[delta]) { int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i]; event[0][x2].emplace_back(i); event[1][x1].emplace_back(i); } } for(int i = 1; i <= n; i++) for(int t = 0; t < 2; t++) { for(auto &j : event[t][i]) { int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[j]; open[y1].push_back(j); close[y2]++; } stack<int> st; for(int j = 1; j <= n; j++) { for(auto &k : open[j]) { trans[t][k] = st.empty() ? 0 : st.top(); st.push(k); } open[j].clear(); while (close[j]--) st.pop(); close[j] = 0; } } int ans = 0; for(int delta = 0; delta < n; delta++) { for(int &i : lst[delta]) { int x1, x2, y1, y2; tie(x1, x2, y1, y2) = rect[i]; dp[i] = (x2 - x1 + 1) * (y2 - y1 + 1); if (trans[0][i]) { // top int j = trans[0][i]; dp[i] = max(dp[i], dp[j] + (get<0> (rect[j]) - x1) * (y2 - y1 + 1)); } // bottom if (trans[1][i]) { int j = trans[1][i]; dp[i] = max(dp[i], dp[j] + (x2 - get<1> (rect[j])) * (y2 - y1 + 1)); } ans = max(ans, dp[i]); } } cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl; 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++) a[i][j] = F[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = F[i - 1][j - 1]; return AC::solve(); } #ifdef ngu int main() { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); int N; assert(1 == scanf("%d", &N)); std::vector<std::vector<int>> F(N, std::vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { assert(1 == scanf("%d", &F[i][j])); } } fclose(stdin); int res = biggest_stadium(N, F); printf("%d\n", res); fclose(stdout); return 0; } #endif // ngu
#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...