제출 #1081066

#제출 시각아이디문제언어결과실행 시간메모리
1081066asdasdqwer축구 경기장 (IOI23_soccer)C++17
6 / 100
693 ms102548 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; #define pii array<int, 2> vector<int> hlp(vector<int> &height) { stack<pii> s; s.push({height[0], 1}); int ar = height[0]; vector<int> ret(height.size()); ret[0] = ar; for (int i=1;i<(int)height.size();i++) { int cnt=1; while (s.size() && height[i] <= s.top()[0]) { auto [he, nm] = s.top();s.pop(); ar -= he * nm; cnt += nm; } ar += cnt * height[i]; s.push({height[i], cnt}); ret[i] = ar; } return ret; } int calc(vector<int> &height) { vector<int> v1 = hlp(height); reverse(height.begin(), height.end()); vector<int> v2 = hlp(height); reverse(height.begin(), height.end()); int n = (int)height.size(); int mx = 0; reverse(v2.begin(), v2.end()); for (int i=0;i<n;i++) { mx = max(mx, v1[i]+v2[i]-height[i]); } return mx; } int biggest_stadium(int N, std::vector<std::vector<int>> F) { vector<vector<int>> up(N, vector<int>(N, 0)); vector<vector<int>> dw = up, lf = up, rt = up; for (int i=0;i<N;i++) { if (F[i][0] == 0) { lf[i][0] = 1; } for (int j=1;j<N;j++) { if (F[i][j] == 1) lf[i][j] = 0; else lf[i][j] = lf[i][j-1] + 1; } if (F[i][N-1] == 0) rt[i][N-1] = 1; for (int j=N-2;j>=0;j--) { if (F[i][j] == 1) rt[i][j] = 0; else rt[i][j] = rt[i][j+1]+1; } } for (int j=0;j<N;j++) { if (F[0][j] == 0) up[0][j] = 1; for (int i=1;i<N;i++) { up[i][j] = up[i-1][j]+1; if (F[i][j] == 1) up[i][j]=0; } if (F[N-1][j] == 0) dw[N-1][j]=1; for (int i=N-2;i>=0;i--) { dw[i][j] = dw[i+1][j]+1; if (F[i][j] == 1) dw[i][j]=0; } } // for (int i=0;i<N;i++) { // for (int j=0;j<N;j++) { // cout << dw[i][j] << " "; // } // cout << "\n"; // } // cout << "here " << endl; int ans = 0; for (int i=0;i<N;i++) { for (int j=0;j<N;j++) { if (F[i][j] == 1) continue; int k = j; vector<int> f1, f2; for (;k<N&&F[i][k]!=1;k++) { f1.push_back(up[i][k]); f2.push_back(dw[i][k]); } ans = max(ans, max(calc(f1), calc(f2))); j = k-1; } } for (int j=0;j<N;j++) { for (int i=0;i<N;i++) { if (F[i][j] == 1) continue; int k = i; vector<int> f1, f2; for (;k<N&&F[k][j]!=1;k++) { f1.push_back(rt[k][j]); f2.push_back(lf[k][j]); } ans = max(ans, max(calc(f1), calc(f2))); i = k-1; } } 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...