Lượng nước tối đa

Points: 1.5 (partial)

Time limit: 1.0s

JAVA11 2.0s

Pypy 3 2.0s

Memory limit: 67M

JAVA11 977M

Pypy 3 977M

Author:

creator

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Mỗi hàng cọc bê tông được đóng sát kín nhau, khi đổ nước vào thì các cọc thấp sẽ chứa nước nếu có những cọc cao ngăn cho.

Ví dụ nếu các cọc bê tông được đóng xếp theo thứ tự $3, 7, 2, 1, 5, 2, 4$ :

Lượng nước

Cho độ dài của $n$ cọc bê tông, giả sử bề ngang của mỗi cọc là một đơn vị, hãy tính lượng nước tối đa mà các cọc bê tông có thể chứa khi được đóng liền thành một hàng, với thứ tự tùy ý.

Đầu vào

Dòng đầu tiên chứa số tự nhiên $n$ $(3 \leq n \leq 2 * 10^{5})$ , số lượng cọc.

Dòng tiếp theo gồm $n$ số nguyên dương không quá $10^{9}$ , chiều cao của mỗi cọc.

Đầu ra

Một số tự nhiên duy nhất là kết quả bài toán.

Subtask

$30 %$ số test có $n \leq 1000$ .

Ví dụ

Đầu vào 1:

Copy

5
1 2 4 4 8

Đầu ra 1:

Copy

Giải thích: Xếp các cọc lần lượt theo thứ tự $4, 1, 2, 4, 8$ cho ta lượng nước lớn nhất là $5$ (nước đọng trên cột $1$ là $3$ khối, đọng trên cột $2$ là $2$ khối).

Đầu vào 2:

Copy

5
5 5 5 5 5

Đầu ra 2:

Copy

QDUY

Comments

2

06082003 commented on April 7, 2023, 9:55 a.m. ← edited →

bai nay hay v