Domino trên biểu đồ Young

Điểm: 7,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một biểu đồ Young — tức một biểu đồ cột gồm $n$ cột có độ cao lần lượt $a_{1}, a_{2}, \dots, a_{n}$ , trong đó $a_{1} \geq a_{2} \geq \dots \geq a_{n} \geq 1$ . Mỗi cột thứ $i$ gồm các ô vuông đơn vị xếp chồng từ đáy lên với tổng cộng $a_{i}$ ô.

Hãy tìm số lượng quân domino không chồng lên nhau lớn nhất có thể đặt vừa vào trong biểu đồ. Mỗi quân domino là một hình chữ nhật kích thước $1 \times 2$ hoặc $2 \times 1$ (đặt nằm ngang hoặc đặt thẳng đứng), và phải nằm hoàn toàn bên trong biểu đồ.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ — số cột của biểu đồ.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — độ cao của các cột.

Dữ liệu ra

In ra một số nguyên — số lượng domino không chồng lên nhau lớn nhất.

Ràng buộc

$1 \leq n \leq 300 000$
$1 \leq a_{i} \leq 300 000$
$a_{i} \geq a_{i + 1}$ với mọi $1 \leq i < n$

Ví dụ

Input	Output	Giải thích
5 3 2 2 2 1	4	Biểu đồ có $3 + 2 + 2 + 2 + 1 = 10$ ô; có thể đặt tối đa $4$ quân domino.
3 3 3 3	4	Biểu đồ vuông $3 \times 3$ với $9$ ô; tối đa $4$ quân domino, còn lại đúng $1$ ô không phủ.
1 1	0	Chỉ có một ô duy nhất, không đặt được domino nào.

Bình luận

Không có bình luận tại thời điểm này.