Submission #1042931

#TimeUsernameProblemLanguageResultExecution timeMemory
104293142kangarooSoccer Stadium (IOI23_soccer)C++17
6 / 100
170 ms35156 KiB
#include "soccer.h" #include "bits/stdc++.h" int biggest_stadium(int N, std::vector<std::vector<int>> F) { using namespace std; using dp_t = vector<vector<vector<int>>>; bool allPos = true; int su = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { su += F[i][j]; } } if (su == 1) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (F[i][j] == 1) { return N * N - min(i + 1, N - i) * min(j + 1, N - j); } } } } else { vector<pair<int, int>> ra(N); vector<int> les(N); for (int i = 0; i < N; ++i) { ra[i].first = 0; for (; ra[i].first < N; ra[i].first++) { if (F[i][ra[i].first] == 0) break; } ra[i].second = N - 1; for (; ra[i].second >= 0; ra[i].second--) { if (F[i][ra[i].second] == 0) break; } les[i] = ra[i].second - ra[i].first + 1; for (int j = ra[i].first; j <= ra[i].second; ++j) { if (F[i][j] == 1) allPos = false; } if (!allPos) break; } int tot = 0; int maI = max_element(les.begin(), les.end()) - les.begin(); pair<int, int> actRa = ra[maI]; pair<int, int> oRa = {maI, maI}; tot = les[maI]; while (allPos && oRa != make_pair(0, N - 1)) { int ne = oRa.first - 1; if (ne < 0 || (oRa.second < N - 1 && les[ne] < les[oRa.second + 1])) ne = oRa.second + 1; if (les[ne] < 0) break; if (actRa.first > ra[ne].first || actRa.second < ra[ne].second) allPos = false; actRa = ra[ne]; tot += les[ne]; oRa = {min(oRa.first, ne), max(oRa.second, ne)}; } if (allPos) return tot; else if (N > 500) return 0; else { vector<vector<int>> prefS(N, vector<int>(N + 1, 0)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { prefS[i][j + 1] = prefS[i][j] + F[i][j]; } } dp_t dpU(N + 1, vector<vector<int>>(N, vector<int>(N, -N * N))); auto dpD = dpU; int ma = 0; for (int i = 0; i <= N; ++i) { for (int j = N - 1; j >= 0; --j) { for (int k = j; k < N; ++k) { if (i == 0)dpU[0][j][k] = 0; else if (prefS[i - 1][k + 1] - prefS[i - 1][j] == 0) dpU[i][j][k] = dpU[i - 1][j][k] + k - j + 1; else dpU[i][j][k] = max(dpU[i][j][k - 1], dpU[i][j + 1][k]); } } } for (int i = N; i >= 0; ++i) { for (int j = N - 1; j >= 0; --j) { for (int k = j; k < N; ++k) { if (i == N) dpD[N][j][k] = 0; else if (prefS[i][k + 1] - prefS[i][j] == 0) { dpD[i][j][k] = dpD[i + 1][j][k] + k - j + 1; ma = max(ma, dpD[i][j][k] + dpU[i + 1][j][k]); } else dpD[i][j][k] = max(dpD[i][j][k - 1], dpD[i][j + 1][k]); } } } return ma; } } }

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:92:1: warning: control reaches end of non-void function [-Wreturn-type]
   92 | }
      | ^
#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...