gwcc2p3

G.W. Coding Contest 2 P3: Speeding Students

Recently, there has been an increase in speeding near G.W Williams. The students and staff both find this very annoying, so the police has decided to implement a new speeding policy.

For \(N\) seconds, the police will measure the speed of the car and will look at \(Q\) queries. Each query two numbers \(A\) and \(B\); if the average speed of the car from second \(A\) to \(B\) is greater than a given number \(M\), then they are considered speeding.

Their fine will be calculated as (average speed-\(M\))\(\times 10\). If multiple queries go over the speed limit the answer will use the highest fine.

Note: average speed is calculated as all instantaneous speeds over the number of instantaneous speeds.
The answer should be rounded down, intermediate calculations should always remain as decimals to maintain accuracy.

Input Specification:

The first line of input will include \(N\), \(Q\), and \(M\). A single car's speed is recorded for \(N\) seconds, where \(N\) is a positive integer \(\{N > 1\}\). \(Q\) is a positive integer representing the number of queries. \(M\) is a positive integer representing the speed limit.

The next \(N\) lines will contain an integer \(\{ < 10^9\}\) representing the speed of the car at each second. The next \(Q\) lines will contain two integers, \(A\) and \(B\). \(A\) is the start time and \(B\) is the end time \(\{ A < B \text{ and } B \leq N, A \geq 1 \}\).

Output Specification:

The output will consist of a single integer, representing the fine the car driver must pay. This value will be rounded down to the nearest integer. If there are no instances of speeding found, output \(-1\)

TIME CONSTRAINT: 1s

Sample Input 1:

6 3 20
15
9
15
26
57
56
1 3
2 4
1 6

Sample Output 1:

Explanation for Sample Input 1:

Calculate the average speed for each query. For the first query (between \(1\) and \(3\) seconds), the average speed is \((15+9+15)/3 = 13\). For the second query, the average speed is \((9+15+26)/3 = 16.667\). For the third query, the average speed is \((15+9+15+26+57+56)/6 = 29.66667\). The highest average speed is \(29.66667\), so that speed will be taken. It is \(29.66667-20 = 9.66667\) km over the speed limit, so the fine is \(9.66667 \times 10 = 96.6667 = 96\).

Sample Input 2:

6 5 100
123
112
157
196
54
23
1 2
4 6
3 6
1 5
3 4

Sample Output 2:

765

Explanation for Sample Input 2:

Calculate the average speed for each query.
Query 1: \((123+112)/2 = 117.5\)
Query 2: \((196+54+23)/3 = 91\)
Query 3: \((157+196+45+23)/4 = 107.5\)
Query 4: \((123+112+157+196+54)/5 = 128.4\)
Query 5: \((157+196)/2 = 176.5\)
The maximum average speed happens on the fifth query. So the fine is \((176.5 - 100) \times 10 = 765\)