Submission #1078611

#TimeUsernameProblemLanguageResultExecution timeMemory
1078611myst6Soccer Stadium (IOI23_soccer)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; /* 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 what if the local maximum isn't strict? can we have another? xx xx xxxxx xxx xxx xx yes we can the stuff on top needs to also have this same pattern though x xx xx xxxxx xxx xxx xx like this is fine but it can't go down then up again x x xxx xxx xxxxx xxx xxx xxx we need to iterate through the heights of the local max now and also the splitting point on the top so now it's O(n^5) how is this still failing wtf? x xx xx xxxxxx <- this is the backbone, then this is accounted for xxxxxx xxx xxx xx let's just check that this is sufficient: - from all nodes on the backbone, change column then row - from all nodes on top, change row then column - from all node below, if going to backbone change row then column else if going to top change column then row so I guess there must be some other extensions... x xxx xxxxx xxx x this isn't accounted for! x xxxx xxxxxx xxx x x xxxx xxxxxxxxx xxxx x ok, if bottom and top maxima are not aligned then obviously gg x xxx xxxx xxxxxxxxxx xxxxxxx xx i think let's consider taking two backbones, the row and the column b xbx xxbx bbbbbbbbbbb xxbxxxx xb as long as the Xs are convex to the structure then yes it works so let's do a dp[col][lo][hi][incr/decr][] : max area as soon as one starts decr the other must as well this dp is like O(n^4) */ const int MAXN = 30; const int inf = 1 << 30; int dp[MAXN][MAXN][MAXN][2]; int pre[MAXN + 1][MAXN]; void chmax(int &x, int y) { x = max(x, y); } int biggest_stadium(int N, vector<vector<int>> F) { // calc prefix sums for (int col=0; col<N; col++) { for (int row=0; row<N; row++) { pre[row + 1][col] += pre[row][col]; pre[row + 1][col] += F[row][col]; } } // fill all with negative inf for (int col=0; col<N; col++) { for (int lo=0; lo<N; lo++) { for (int hi=lo; hi<N; hi++) { for (int f=0; f<2; f++) { dp[col][lo][hi][f] = -inf; } } } } // base case, col=0 for (int lo=0; lo<N; lo++) { for (int hi=lo; hi<N; hi++) { for (int f=0; f<2; f++) { int ones = pre[hi + 1][0] - pre[lo][0]; if (ones == 0) { dp[0][lo][hi][f] = hi - lo + 1; } } } } // transition one col to the next for (int col=0; col<N-1; col++) { for (int lo=0; lo<N; lo++) { for (int hi=lo; hi<N; hi++) { if (dp[col][lo][hi][0] > 0) { for (int lo2=lo; lo2>=0; lo2--) { for (int hi2=hi; hi2<N; hi2++) { int ones = pre[hi2 + 1][col + 1] - pre[lo2][col + 1]; if (ones > 0) break; chmax(dp[col+1][lo2][hi2][0], dp[col][lo][hi][0] + hi2 - lo2 + 1); chmax(dp[col+1][lo2][hi2][1], dp[col][lo][hi][0] + hi2 - lo2 + 1); } } } if (dp[col][lo][hi][1] > 0) { for (int lo2=lo; lo2<N; lo2++) { for (int hi2=hi; hi2>=lo2; hi2--) { int ones = pre[hi2 + 1][col + 1] - pre[lo2][col + 1]; if (ones > 0) break; chmax(dp[col+1][lo2][hi2][1], dp[col][lo][hi][1] + hi2 - lo2 + 1); } } } } } } // get answer int ans = 0; for (int col=0; col<N; col++) { for (int lo=0; lo<N; lo++) { for (int hi=lo; hi<N; hi++) { for (int f=0; f<2; f++) { chmax(ans, dp[col][lo][hi][f]); } } } } return ans; } /* 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...