This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C" #include <vector> #include <iostream> #include <stack> using namespace std; #include "../../lib/17-rectangle/MaximumRectangle.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N; cin >> N; vector<long long> A(N); for(int i=0;i<N;++i) cin >> A[i]; cout << MaximumRectangle(A) << endl; return 0; }
#line 1 "test/rectangle/MaximumRectangle-2.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C" #include <vector> #include <iostream> #include <stack> using namespace std; #line 1 "lib/17-rectangle/MaximumRectangle.cpp" /* * @title MaximumRectangle - 最大長方形 * @docs md/rectangle/MaximumRectangle.md */ long long MaximumRectangle(vector<long long> ar){ ar.push_back(0); stack<pair<long long,long long>> st; long long res = 0; for(long long r = 0; r < ar.size(); ++r){ long long vr = ar[r]; long long x = r; while(st.size() && st.top().first > vr) { auto [vl, l] = st.top(); st.pop(); x = l; res = max(res,vl*(r - l)); } if(st.empty() || (st.size() && st.top().first < vr)) st.push({vr,x}); } return res; } #line 8 "test/rectangle/MaximumRectangle-2.test.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N; cin >> N; vector<long long> A(N); for(int i=0;i<N;++i) cin >> A[i]; cout << MaximumRectangle(A) << endl; return 0; }