test/MaximumRectangle.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_C

Depends on

• DP/MaximumRectangle.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_C"
#include "./../DP/MaximumRectangle.cpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	using ll = long long;

	int n;
	cin >> n;
	vector<ll> a(n);
	for (ll& i : a) {
		cin >> i;
	}
	cout << MaximumRectangle(a) << '\n';
}

#line 1 "test/MaximumRectangle.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_C"
#line 2 "DP/MaximumRectangle.cpp"
#include <vector>
#include <stack>
#include <algorithm>

template <class T> T MaximumRectangle(const std::vector<T>& a) {
	int n = a.size();
	T result = 0;
	std::stack<int> st;
	std::vector<int> L(n), R(n);
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && a[st.top()] >= a[i]) st.pop();
		L[i] = st.empty() ? 0 : st.top() + 1;
		st.push(i);
	}
	while (!st.empty()) st.pop();
	for (int i = n - 1; i >= 0; --i) {
		while (!st.empty() && a[st.top()] >= a[i]) st.pop();
		R[i] = st.empty() ? n : st.top();
		st.push(i);
	}
	for (int i = 0; i < n; ++i) {
		result = std::max(result, a[i] * (R[i] - L[i]));
	}
	return result;
}
#line 3 "test/MaximumRectangle.test.cpp"
#include <iostream>
#line 5 "test/MaximumRectangle.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	using ll = long long;

	int n;
	cin >> n;
	vector<ll> a(n);
	for (ll& i : a) {
		cin >> i;
	}
	cout << MaximumRectangle(a) << '\n';
}

Back to top page