2465. Hay Expenses

单点时限: 2.0 sec

内存限制: 256 MB

Every day Farmer John feeds the cows a lavish meal of premium gourmet hay. He then records the number of bales on the next line of his expense notebook.

When tax time comes, FJ realizes that he neglected to record the dates for the hay feedings. He must calculate a number of different totals of successive hay feedings in order to solve the puzzle of which feedings went with which month of expenses.

FJ has created a dataset with N (4 <= N <= 500) days conveniently numbered 1..N of hay bale counts H_i (1 <= H_i <= 1,000). He has an additional Q (1 <= Q <= 500) queries – each query is a pair of integers S_j and E_j (1 <= S_j <= E_j <= N) that denote that start

and end indices of some hay bale counts. Your job is to sum the hay bale counts for the days S_j..E_j (inclusive) and report one sum for each query.

输入格式

  • Line 1: Two space-separated integers: N and Q

  • Lines 2..N+1: Line i+1 contains a single hay bale count for day i:

H_i

  • Lines N+2..N+Q+1: Line j+N+1 describes query j with a pair of

integers: S_j and E_j

输出格式

  • Lines 1..Q: Line j of the output file contains a single integer that

is the sum of the hay bale counts for days S_j through E_j

样例

Input
4 2
5
8
12
6
1 3
2 4
INPUT DETAILS:
Four days; two queries. Bale counts: 5, 8, 12, and 6. Count
Days 1..3 and 2..4.
Output
25
26
OUTPUT DETAILS:
Days: 1 2 3 4
Counts: 5 8 12 6
query 1..3: 5 + 8 + 12 = 25
query 2..4: 8 + 12 + 6 = 26

7 人解决,14 人已尝试。

8 份提交通过,共有 19 份提交。

7.1 EMB 奖励。

创建: 11 年,6 月前.

修改: 3 年前.

最后提交: 2 年,3 月前.

来源: USACO 2008 DEC

题目标签