SUMF - SUMF
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: adminchg
Với một dãy số p bất kì gồm k phần tử, ta định nghĩa hàm f(p) như sau:
- Nếu k =1 thì f(p) = 0
- Ngược lại, f(p) là giá trị
lớn nhất với mọi 1 ≤ i < j ≤ k.
Cho một dãy số a gồm n phần tử. Hãy tính:
Với a[l..r] là dãy con gồm các phần tử từ vi trí l đến vi trí r của a.
Input:
- Dòng đầu tiên gồm số nguyên n (1 ≤ n ≤ 2.105) là số phần tử của dãy a.
- Dòng thứ hai gồm n số nguyên a1, a2,..., an (1 ≤ ai ≤ 108) là các phần tử của dãy a.
Output: In ra giá tri S cần tìm.
Ràng buộc:
- Subtask 1: 15% số test của bài có n ≤ 80;
- Subtask 2: 15% số test của bài có n ≤ 300;
- Subtask 3: 20% số test của bài có n ≤ 5000;
Subtask 4: 50% số test của bài có: Không có giới hạn gì thêm
Ví dụ
| Input | Output |
|
3 4 5 2 |
7 |
|
4 10 10 10 10 |
0 |
|
7 2 6 8 1 5 10 3 |
129 |
• ở Test01 ta có:
- f(a[1..1]) = f([4]) = 0
- f(a[1..2]) = f([4, 5]) = 1
- f(a[1..3]) = f([4, 5, 2]) = 3
- f(a[2..2]) = f([5]) = 0
- f(a[2..3])=f([5, 2]) =3
- f(a[3..3])=f([2]) =0
=> S=0 + 1 + 3 + 0 + 3 + 0 = 7.
Bài tập mới