Phát kẹo theo thứ hạng
Points
33
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Có $N$ học sinh đứng thành một hàng ngang, học sinh thứ $i$ có điểm đánh giá $r_i$. Giáo viên muốn phát kẹo cho các học sinh theo hai quy tắc:
- Mỗi học sinh phải nhận được ít nhất $1$ viên kẹo.
- Nếu một học sinh có điểm đánh giá cao hơn hẳn học sinh đứng ngay cạnh mình, học sinh đó phải nhận được nhiều kẹo hơn người kia.
Hãy tìm tổng số viên kẹo ít nhất mà giáo viên cần chuẩn bị.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- Dòng thứ hai chứa $N$ số nguyên $r_1, r_2, \dots, r_N$.
Dữ liệu ra
Một số nguyên duy nhất là tổng số viên kẹo ít nhất cần chuẩn bị.
Ví dụ
| Input | Output |
|---|---|
| 3\n1 0 2 | 5 |
| 3\n1 2 2 | 4 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le r_i \le 10^9$
Community Discussion