test/aoj/DPL_3_C.test.cpp

View this file on GitHub
Last update: 2024-09-01 11:17:48+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_C

Depends on

Cartesian-Tree (src/Misc/CartesianTree.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_C
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <src/Misc/CartesianTree.hpp>
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<long long> h(N);
 for (int i= 0; i < N; ++i) cin >> h[i];
 CartesianTree ct(h);
 long long ans= 0;
 for (int i= 0; i < N; ++i) {
  auto [l, r]= ct.range(i);
  ans= max(ans, h[i] * (r - l));
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/DPL_3_C.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_C
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <src/Misc/CartesianTree.hpp>
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<long long> h(N);
 for (int i= 0; i < N; ++i) cin >> h[i];
 CartesianTree ct(h);
 long long ans= 0;
 for (int i= 0; i < N; ++i) {
  auto [l, r]= ct.range(i);
  ans= max(ans, h[i] * (r - l));
 }
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	3 MB
g++-13	00_sample_01.in	AC	4 ms	4 MB
g++-13	01_small_00.in	AC	4 ms	4 MB
g++-13	01_small_01.in	AC	4 ms	4 MB
g++-13	02_corner_00.in	AC	4 ms	4 MB
g++-13	02_corner_01.in	AC	4 ms	4 MB
g++-13	02_corner_02.in	AC	4 ms	4 MB
g++-13	02_corner_03.in	AC	4 ms	4 MB
g++-13	02_corner_04.in	AC	4 ms	4 MB
g++-13	02_corner_05.in	AC	4 ms	4 MB
g++-13	03_wide_00.in	AC	4 ms	4 MB
g++-13	03_wide_01.in	AC	4 ms	4 MB
g++-13	03_wide_02.in	AC	4 ms	3 MB
g++-13	04_tall_00.in	AC	4 ms	3 MB
g++-13	04_tall_01.in	AC	4 ms	4 MB
g++-13	04_tall_02.in	AC	4 ms	4 MB
g++-13	05_rand_00.in	AC	4 ms	4 MB
g++-13	05_rand_01.in	AC	4 ms	4 MB
g++-13	05_rand_02.in	AC	4 ms	3 MB
g++-13	05_rand_03.in	AC	4 ms	4 MB
g++-13	05_rand_04.in	AC	4 ms	4 MB
g++-13	05_rand_05.in	AC	4 ms	3 MB
g++-13	05_rand_06.in	AC	4 ms	4 MB
g++-13	05_rand_07.in	AC	4 ms	4 MB
g++-13	06_ordered_00.in	AC	11 ms	7 MB
g++-13	06_ordered_01.in	AC	11 ms	7 MB
g++-13	07_unique_00.in	AC	11 ms	7 MB
g++-13	07_unique_01.in	AC	12 ms	7 MB
g++-13	08_large_00.in	AC	12 ms	7 MB
g++-13	08_large_01.in	AC	14 ms	7 MB
g++-13	08_large_02.in	AC	14 ms	7 MB
g++-13	08_large_03.in	AC	14 ms	7 MB
g++-13	08_large_04.in	AC	14 ms	7 MB
g++-13	08_large_05.in	AC	14 ms	7 MB
g++-13	09_corner_00.in	AC	13 ms	7 MB
g++-13	09_corner_01.in	AC	12 ms	6 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	00_sample_01.in	AC	4 ms	4 MB
clang++-18	01_small_00.in	AC	4 ms	4 MB
clang++-18	01_small_01.in	AC	4 ms	4 MB
clang++-18	02_corner_00.in	AC	4 ms	4 MB
clang++-18	02_corner_01.in	AC	4 ms	4 MB
clang++-18	02_corner_02.in	AC	4 ms	4 MB
clang++-18	02_corner_03.in	AC	4 ms	4 MB
clang++-18	02_corner_04.in	AC	5 ms	4 MB
clang++-18	02_corner_05.in	AC	4 ms	4 MB
clang++-18	03_wide_00.in	AC	4 ms	4 MB
clang++-18	03_wide_01.in	AC	4 ms	4 MB
clang++-18	03_wide_02.in	AC	4 ms	4 MB
clang++-18	04_tall_00.in	AC	4 ms	4 MB
clang++-18	04_tall_01.in	AC	4 ms	4 MB
clang++-18	04_tall_02.in	AC	4 ms	4 MB
clang++-18	05_rand_00.in	AC	4 ms	4 MB
clang++-18	05_rand_01.in	AC	4 ms	4 MB
clang++-18	05_rand_02.in	AC	4 ms	4 MB
clang++-18	05_rand_03.in	AC	4 ms	4 MB
clang++-18	05_rand_04.in	AC	4 ms	4 MB
clang++-18	05_rand_05.in	AC	4 ms	4 MB
clang++-18	05_rand_06.in	AC	4 ms	4 MB
clang++-18	05_rand_07.in	AC	4 ms	4 MB
clang++-18	06_ordered_00.in	AC	10 ms	7 MB
clang++-18	06_ordered_01.in	AC	11 ms	6 MB
clang++-18	07_unique_00.in	AC	11 ms	6 MB
clang++-18	07_unique_01.in	AC	11 ms	6 MB
clang++-18	08_large_00.in	AC	12 ms	6 MB
clang++-18	08_large_01.in	AC	13 ms	6 MB
clang++-18	08_large_02.in	AC	14 ms	6 MB
clang++-18	08_large_03.in	AC	14 ms	6 MB
clang++-18	08_large_04.in	AC	14 ms	6 MB
clang++-18	08_large_05.in	AC	13 ms	6 MB
clang++-18	09_corner_00.in	AC	12 ms	6 MB
clang++-18	09_corner_01.in	AC	12 ms	6 MB