시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.2 초 | 1024 MB | 95 | 8 | 6 | 12.245% |
A group of n bunnies found a garden with n carrots, arranged in a row. Both the bunnies and the carrots are numbered with integers from 1 to n. The bunnies have made preliminary evaluation for the sweetness of the carrots, which are expressed with the integers a1, ..., an (some carrots may be spoiled and can have negative number for sweetness). The soil under only one carrot p is fertilized and this changes the sweetness of this carrot by an integer s. More precisely, the real sweetness of carrot p is ap + s.
Unfortunately, p and s are unknown to rabbits. However, they have massumptions about the pair of values (p, s).
Bunny number k makes jumps of length k, i.e. collects the carrots in positions that are multiples of k.
For each assumption j, they look for the maximum amount tj of the total real sweetness of the carrots that can be collected by a bunny. Help them by writing program maxs that finds the sum of the values of tj for all assumptions.
From the first line of the standard input, your program reads an integer n - the number of carrots (and bunnies). From the next line read n integers a1, ..., an - the preliminary evaluation of the sweetness of the carrots. From the next line read an integer m-the number of assumptions. From each of the next mlines, read two integers p and s – carrot's index and its’ sweetness change for the corresponding assumption.
On one line of the standard output, print a number equal to t1 + ... + tm, where tj is the maximum sum of carrots' sweetness under the j-th assumption.
번호 | 배점 | 제한 |
---|---|---|
1 | 13 | n ≤ 5×103, m ≤ 5×103 |
2 | 21 | n ≤ 1.5×104, m ≤ 3.5×103 |
3 | 25 | n ≤ 5×104, m ≤ 2×105, Only non-negative changes in any sweetness s. |
4 | 30 | n ≤ 5×104, m ≤ 2×105 |
5 | 11 | n ≤ 5×104, m ≤ 5×105 |
6 2 -5 3 2 -1 4 2 3 -4 2 3
12
According to the first assumption, carrots have sweetness 2, -5, -1, 2, -1, 4.
Bunny 1 collects total sweetness 2 + (-5) + (-1) + 2 + (-1) + 4 = 1.
Bunny 2 collects total sweetness (-5) + 2 + 4 = 1.
Bunny 3 collects total sweetness (-1) + 4 = 3.
Bunny 4 collects total sweetness 2.
Bunny 5 collects total sweetness of -1.
Bunny 6 collects total sweetness 4.
Therefore t1 = 4.
According to the second assumption, carrots have sweetness 2, -2, 3, 2, -1, 4. Bunnies collect sweetness 8, 4, 7, 2, -1, 4, respectively.
Therefore t2 = 8.
The final answer is 4 + 8 = 12.