Submission #843885

#TimeUsernameProblemLanguageResultExecution timeMemory
843885wiiSoccer Stadium (IOI23_soccer)C++17
6 / 100
378 ms132992 KiB
// #define testing #ifdef testing #include <cassert> #include <cstdio> #include <vector> #include <iostream> #else #include "soccer.h" #endif //testing using namespace std; #define foru(i,a,b) for(int i = (a); i <= (b); ++i) #define ford(i,a,b) for(int i = (a); i >= (b); --i) const int MaxN = 2e3 + 5; int n; int a[MaxN][MaxN]; int l[MaxN][MaxN], r[MaxN][MaxN], sum[MaxN][MaxN], nxt[MaxN][MaxN], ans[MaxN][MaxN]; int get(int u, int v, int val, int arr[MaxN][MaxN]) { int &x = nxt[u][v]; return arr[x][v] > val ? x = get(x, v, val, arr) : x; } int sol() { int res = 0; foru(i, 1, n) foru(j, 1, n) ans[i][j] = 0; foru(i, 1, n) { foru(j, 1, n) l[i][j] = (a[i][j] ? 0 : l[i][j - 1] + 1); ford(j, n, 1) r[i][j] = (a[i][j] ? 0 : r[i][j + 1] + 1); } foru(i, 1, n) { foru(j, 1, n) if (a[i][j] == 0) { sum[i][j] = 0; nxt[i][j] = i - 1; int prv = get(i, j, l[i][j], l); sum[i][j] = sum[prv][j] + l[i][j] * (i - prv); ans[i][j] += sum[i][j]; } } foru(i, 1, n) { foru(j, 1, n) if (a[i][j] == 0) { sum[i][j] = 0; nxt[i][j] = i - 1; int prv = get(i, j, r[i][j], r); sum[i][j] = sum[prv][j] + r[i][j] * (i - prv); ans[i][j] += sum[i][j]; } } ford(i, n, 1) { foru(j, 1, n) if (a[i][j] == 0) { sum[i][j] = 0; nxt[i][j] = i + 1; int prv = get(i, j, l[i][j], l); sum[i][j] = sum[prv][j] + l[i][j] * -(i - prv); ans[i][j] += sum[i][j]; } } ford(i, n, 1) { foru(j, 1, n) if (a[i][j] == 0) { sum[i][j] = 0; nxt[i][j] = i + 1; int prv = get(i, j, r[i][j], r); sum[i][j] = sum[prv][j] + r[i][j] * -(i - prv); ans[i][j] += sum[i][j]; } } foru(i, 1, n) foru(j, 1, n) sum[i][j] = (a[i][j] ? 0 : sum[i - 1][j] + 1), ans[i][j] -= sum[i][j]; ford(i, n, 1) foru(j, 1, n) sum[i][j] = (a[i][j] ? 0 : sum[i + 1][j] + 1), ans[i][j] -= sum[i][j]; foru(i, 1, n) foru(j, 1, n) if (a[i][j] == 0) ans[i][j] -= l[i][j] + r[i][j]; foru(i, 1, n) foru(j, 1, n) if (a[i][j] == 0) res = max(res, ans[i][j] + 1); return res; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { n = N; foru(i, 0, n + 1) foru(j, 0, n + 1) a[i][j] = 1; foru(i, 1, n) foru(j, 1, n) a[i][j] = F[i - 1][j - 1]; int ans = 0; ans = max(ans, sol()); // rotation // ans = max(ans, sol()); return ans; } #ifdef testing int main() { if (fopen("01.in", "r")) { freopen("01.in", "r", stdin); freopen("01.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
#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...