Submission #1078585

#TimeUsernameProblemLanguageResultExecution timeMemory
1078585myst6Soccer Stadium (IOI23_soccer)C++17
13.50 / 100
4550 ms58392 KiB
#include <bits/stdc++.h> using namespace std; bool dp[4][2005][2005]; /* let's consider the bottom edge we must be able to reach all other cells with an up kick then left kick a rectangle is a valid field because yes if any two filled positions on same row or col have a tree between them then no if we fill in all empty spaces and consider that whole square we see that the trees form either strict decreasing or strict increasing thingies xx.. xxx. .xxx ..xx still bad consider top-left one it needs to either have access to all rows or all cols xxxx xxxx .xxx ..xx now good xxxx .xxx ..xx .... still good so, one side needs to be completely filled in if we can solve where the top side is completely full, then rotate 90deg 4 times xxxx .xxx ..xx ...x now, restriction on rest is? it must be increasing then decreasing section xxxxxxxx .xxxxx.x ..xxx..x ...xx..x let's say we have down[i][j] : how far down we can go from here for a given row, let's say position k is the local maximum then we do a greedy on both sides to calculate scores so O(n^2) per row so O(n^3) in total where does this account for something like x x xxxxx x x x xxx xxxxx x x I think in addition to the backbone and stalagmites we can have one prong upwards xxxxx xxx xx x x x xxxxx xxx xx x i think the prong needs to be above the splitting point, too otherwise, there's a column we can't reach */ const int MAXN = 2000; int down[MAXN][MAXN]; int up[MAXN][MAXN]; int solve(int N, vector<vector<int>> F) { for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { // go as far down as possible in O(n^3) for (int k=i; k<N; k++) { if (F[k][j] == 1) break; down[i][j] = k-i+1; } // go as far up as possible in O(n^3) for (int k=i; k>=0; k--) { if (F[k][j] == 1) break; up[i][j] = i-k+1; } } } int best = 0; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (F[i][j] == 1) continue; // choose position (i, j) as the splitting point on row i int ans = down[i][j] + up[i][j] - 1; // go left { int curr = down[i][j]; for (int k=j-1; k>=0; k--) { if (F[i][k] == 1) break; curr = min(curr, down[i][k]); ans += curr; } } // go right { int curr = down[i][j]; for (int k=j+1; k<N; k++) { if (F[i][k] == 1) break; curr = min(curr, down[i][k]); ans += curr; } } best = max(best, ans); } } return best; } vector<vector<int>> rotate(int N, vector<vector<int>> F) { vector<vector<int>> G(N, vector<int>(N)); for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { G[i][j] = F[N-1-j][i]; } } return G; } int biggest_stadium(int N, vector<vector<int>> F) { int best = 0; for (int i=0; i<4; i++) { best = max(best, solve(N, F)); F = rotate(N, F); } return best; } /* 5 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 */
#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...