test/verify/aoj-dpl-3-c.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 10:46:05+00:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C

Depends on

• Largest Rectangle (最大長方形) (dp/largest-rectangle.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C
// clang-format on

#include <iostream>
#include <vector>

#include "../../dp/largest-rectangle.hpp"

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> h(N);
  for (int& height : h) cin >> height;
  cout << largest_rectangle(h) << endl;
}

#line 1 "test/verify/aoj-dpl-3-c.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C
// clang-format on

#include <iostream>
#include <vector>

#line 2 "dp/largest-rectangle.hpp"

#include <algorithm>
#include <cstdint>
#include <stack>
#line 7 "dp/largest-rectangle.hpp"

template <typename T>
std::int64_t largest_rectangle(std::vector<T> height) {
  std::stack<int> st;
  height.push_back(0);
  std::vector<int> left(height.size());
  std::int64_t ret = 0;
  for (int i = 0; i < height.size(); i++) {
    while (!st.empty() && height[st.top()] >= height[i]) {
      ret = std::max(ret,
                     (std::int64_t)(i - left[st.top()] - 1) * height[st.top()]);
      st.pop();
    }
    left[i] = st.empty() ? -1 : st.top();
    st.emplace(i);
  }
  return (ret);
}
#line 9 "test/verify/aoj-dpl-3-c.test.cpp"

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> h(N);
  for (int& height : h) cin >> height;
  cout << largest_rectangle(h) << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	2 ms	4 MB
g++	00_sample_01	AC	2 ms	4 MB
g++	01_small_00	AC	2 ms	4 MB
g++	01_small_01	AC	2 ms	3 MB
g++	02_corner_00	AC	2 ms	4 MB
g++	02_corner_01	AC	2 ms	4 MB
g++	02_corner_02	AC	2 ms	4 MB
g++	02_corner_03	AC	2 ms	4 MB
g++	02_corner_04	AC	2 ms	4 MB
g++	02_corner_05	AC	2 ms	4 MB
g++	03_wide_00	AC	2 ms	4 MB
g++	03_wide_01	AC	2 ms	4 MB
g++	03_wide_02	AC	2 ms	4 MB
g++	04_tall_00	AC	2 ms	4 MB
g++	04_tall_01	AC	2 ms	3 MB
g++	04_tall_02	AC	2 ms	4 MB
g++	05_rand_00	AC	2 ms	4 MB
g++	05_rand_01	AC	2 ms	4 MB
g++	05_rand_02	AC	2 ms	3 MB
g++	05_rand_03	AC	2 ms	4 MB
g++	05_rand_04	AC	2 ms	4 MB
g++	05_rand_05	AC	2 ms	4 MB
g++	05_rand_06	AC	2 ms	4 MB
g++	05_rand_07	AC	2 ms	3 MB
g++	06_ordered_00	AC	21 ms	5 MB
g++	06_ordered_01	AC	21 ms	4 MB
g++	07_unique_00	AC	21 ms	4 MB
g++	07_unique_01	AC	21 ms	4 MB
g++	08_large_00	AC	30 ms	4 MB
g++	08_large_01	AC	31 ms	4 MB
g++	08_large_02	AC	31 ms	4 MB
g++	08_large_03	AC	31 ms	4 MB
g++	08_large_04	AC	31 ms	4 MB
g++	08_large_05	AC	31 ms	4 MB
g++	09_corner_00	AC	33 ms	4 MB
g++	09_corner_01	AC	34 ms	4 MB
clang++	00_sample_00	AC	2 ms	4 MB
clang++	00_sample_01	AC	2 ms	4 MB
clang++	01_small_00	AC	2 ms	4 MB
clang++	01_small_01	AC	2 ms	4 MB
clang++	02_corner_00	AC	2 ms	4 MB
clang++	02_corner_01	AC	2 ms	4 MB
clang++	02_corner_02	AC	2 ms	4 MB
clang++	02_corner_03	AC	2 ms	4 MB
clang++	02_corner_04	AC	2 ms	4 MB
clang++	02_corner_05	AC	2 ms	4 MB
clang++	03_wide_00	AC	2 ms	4 MB
clang++	03_wide_01	AC	2 ms	4 MB
clang++	03_wide_02	AC	2 ms	4 MB
clang++	04_tall_00	AC	2 ms	4 MB
clang++	04_tall_01	AC	2 ms	4 MB
clang++	04_tall_02	AC	2 ms	4 MB
clang++	05_rand_00	AC	2 ms	4 MB
clang++	05_rand_01	AC	2 ms	4 MB
clang++	05_rand_02	AC	2 ms	4 MB
clang++	05_rand_03	AC	2 ms	4 MB
clang++	05_rand_04	AC	2 ms	4 MB
clang++	05_rand_05	AC	2 ms	4 MB
clang++	05_rand_06	AC	2 ms	4 MB
clang++	05_rand_07	AC	2 ms	4 MB
clang++	06_ordered_00	AC	21 ms	5 MB
clang++	06_ordered_01	AC	21 ms	5 MB
clang++	07_unique_00	AC	21 ms	4 MB
clang++	07_unique_01	AC	22 ms	5 MB
clang++	08_large_00	AC	31 ms	4 MB
clang++	08_large_01	AC	31 ms	5 MB
clang++	08_large_02	AC	31 ms	4 MB
clang++	08_large_03	AC	31 ms	5 MB
clang++	08_large_04	AC	31 ms	4 MB
clang++	08_large_05	AC	31 ms	5 MB
clang++	09_corner_00	AC	33 ms	5 MB
clang++	09_corner_01	AC	33 ms	5 MB

Back to top page