This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 長さ N のヒストグラムの長方形領域最大 // Verified: AOJ DPL_3_C: Largest Rectangle in a Histogram int histArea(vector<int> h) { // 番兵 int N = h.size(); h.push_back(0); N++; // height, position int ans = 0; stack<pii> S; rep(i,0,N+1) { if(S.empty()) S.push(pii(h[i], i)); if (S.top().first < h[i]) S.push(pii(h[i], i)); else if(S.top().first > h[i]) { int lastpos = 0; while(!S.empty() && S.top().first >= h[i]) { lastpos = S.top().second; chmax(ans, S.top().first * (i-lastpos)); S.pop(); } S.push(pii(h[i], lastpos)); } } return ans; }
#line 1 "dp/dp_003_histogram.cpp" // 長さ N のヒストグラムの長方形領域最大 // Verified: AOJ DPL_3_C: Largest Rectangle in a Histogram int histArea(vector<int> h) { // 番兵 int N = h.size(); h.push_back(0); N++; // height, position int ans = 0; stack<pii> S; rep(i,0,N+1) { if(S.empty()) S.push(pii(h[i], i)); if (S.top().first < h[i]) S.push(pii(h[i], i)); else if(S.top().first > h[i]) { int lastpos = 0; while(!S.empty() && S.top().first >= h[i]) { lastpos = S.top().second; chmax(ans, S.top().first * (i-lastpos)); S.pop(); } S.push(pii(h[i], lastpos)); } } return ans; }