시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 106 | 45 | 40 | 40.000% |
There is a very long straight road, which consists of N sections numbered from 1 through N. Each section has specific firmness, and the firmness of the section i (1 ≤ i ≤ N) is Ai.
JOI-kun, the gifted sport star, is going to play triple jump. A triple jump consists of three consecutive jumps. Let a, b, c be the numbers of sections at which JOI-kun takes off, then the following conditions should be met.
JOI-kun is going to perform Q triple jumps. In the j-th (1 ≤ j ≤ Q) triple jump, he should take off at sections whose numbers are in the range of Lj to Rj. In other words, Lj ≤ a < b < c ≤ Rj must be hold.
JOI-kun wants to take off at firmer sections. For each triple jump, JOI-kun is curious to know the maximum sum of firmness of the sections at which JOI-kun takes off.
Write a program that, given the number of sections and the information of triple jumps, calculates for each triple jump the maximum sum of firmness of the sections at which JOI-kun takes off.
Read the following data from the standard input. All the values in the input are integers.
N A1 A2 · · · AN Q L1 R1 L2 R2 . . . LQ RQ
Write Q lines to the standard output. The j-th (1 ≤ j ≤ Q) line should contain the maximum sum of firmness of the sections at which JOI-kun takes off in the j-th triple jump.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | N ≤ 100, Q ≤ 100. |
2 | 14 | N ≤ 5 000. |
3 | 27 | N ≤ 200 000, Q = 1, L1 = 1, R1 = N. |
4 | 54 | No additional constraints. |
5 5 2 1 5 3 3 1 4 2 5 1 5
12 9 12
In the first jump, JOI-kun can achieve the maximum sum of 12 by taking off at the sections 1, 2 and 4.
In the second jump, JOI-kun can achieve the maximum sum of 9 by taking off at the sections 3, 4 and 5. If he takes off at the sections 2, 4 and 5, the sum of firmness is 10, but b − a ≤ c − b is not satisfied.
In the third jump, JOI-kun can achieve the maximum sum of 12 by taking off at the sections 1, 2 and 4. If he takes off at the sections 1, 4 and 5, the sum of firmness is 13, but b − a ≤ c − b is not satisfied.
5 5 4 4 5 4 1 1 5
14
15 12 96 100 61 54 66 37 34 58 21 21 1 13 50 81 12 1 15 3 12 11 14 1 13 5 9 4 6 6 14 2 5 4 15 1 7 1 10 8 13
277 227 72 262 178 181 174 257 208 262 262 113