Submission #1205811

#TimeUsernameProblemLanguageResultExecution timeMemory
1205811PacybwoahSoccer Stadium (IOI23_soccer)C++20
0 / 100
0 ms324 KiB
#include "soccer.h" #include<iostream> #include<vector> #include<algorithm> #include<utility> using namespace std; typedef long long ll; int biggest_stadium(int N, std::vector<std::vector<int>> F){ int n = N, ans = 0; vector<vector<int>> vec(n + 1, vector<int>(n + 1)), pre(n + 1, vector<int>(n + 1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ vec[i][j] = F[i - 1][j - 1]; ans += vec[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + vec[i][j]; } } auto get = [&](int a, int b, int c, int d){ // (a, b) -> (c, d) return pre[c][d] - pre[c][b - 1] - pre[a - 1][d] + pre[a - 1][b - 1]; }; vector<pair<int, pair<int, int>>> rngs; for(int i = 1; i <= n; i++){ int mini = n + 1, maxi = 0; for(int j = 1; j <= n; j++){ if(vec[i][j] == 1){ mini = min(mini, j); maxi = max(maxi, j); } } if(mini > maxi) continue; if(get(i, mini, i, maxi) != maxi - mini + 1) return 0; rngs.emplace_back(i, make_pair(mini, maxi)); } int sz = (int)rngs.size(); for(int i = 0; i < sz; i++){ for(int j = i + 1; j < sz; j++){ auto &[l, r] = rngs[i].second; auto &[tl, tr] = rngs[j].second; int ul = max(l, tl), ur = min(r, tr); if((l != ul || r != ur) && (tl != ul || tr != ur)) return 0; int t = rngs[i].first, b = rngs[j].first; if(get(t, ul, b, ur) != (b - t + 1) * (ur - ul + 1)) return 0; } } return ans; }
#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...