Bài 3: (5 điểm)
Cho một dãy số gồm N phần tử nguyên dương và cặp số L và R (1<=L<R<=N). Em hãy chia đoạn con từ L đến R thành hai phần sao cho tổng chênh lệch giữa hai phần của mỗi đoạn con là nhỏ nhất. Biết rằng hai phần này là tổng của các số nằm liên tiếp với nhau trong đoạn con đó.
Dữ liệu vào: File văn bản CHIADOAN.INP gồm:
- Dòng 1 chứa hai số nguyên N, Q (1<N<=105; 1<Q<=105)
- Dòng 2 gồm N số nguyên dương ai (ai <=109, 1<i<=N)
- Q dòng tiếp theo, mỗi dòng gồm một cặp số nguyên L, R
Dữ liệu ra: File văn bản CHIADOAN.OUT gồm:
- Gồm Q dòng, mỗi dòng là độ chênh lệch nhỏ nhất khi chia ra đoạn con tương ứng.
|
CHIADOAN.INP |
CHIADOAN.OUT |
|
5 2 7 1 4 2 5 2 5 1 4 |
2 0
|
Giới hạn:
- Có 50% số test có N<= 1000 và Q <=1000
- Có 50% số test còn lại không ràng buộc gì thêm
Giải thích:
- Trong đoạn con thứ nhất [2,5] có cách chia ra đoạn [2,3] và đoạn [4,5] với tổng độ chênh lệch nhỏ nhất của 2 đoạn là: 2
- Trong đoạn con thứ hai [1,4] có cách chia ra đoạn [1,1] và đoạn [2,4] với tổng độ chênh lệch nhỏ nhất của 2 đoạn là: 0