1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//
//  Created by Kamil Borzym on 28/09/15.
//  Copyright © 2015 kam800. All rights reserved.
//

#include "stdio.h"
#include "stdlib.h"

// 1 ≤ n, m ≤ 500 000
// 1 ≤ ai ≤ 10^6

int main() {
    long i, j;

    long n, m;
    scanf("%ld %ld", &n, &m);

    long *a = malloc(sizeof(long) * n);

    for (i=0; i<n; ++i) {
        long ai;
        scanf("%ld", &ai);
        a[i] = ai;
    }

    long long *field = calloc(n, sizeof(long long));
    long long clock = 0;

    for (i=0; i<m; ++i) {
        long long di, bi;
        scanf("%lld %lld", &di, &bi);

        long long crop = 0;
        long long timeDelta = di - clock;
        for (j=0; j<n; ++j) {
            long long height = field[j] + a[j] * timeDelta;
            if (height > bi) {
                crop += (height - bi);
                height = bi;
            }
            field[j] = height;
        }
        printf("%lld\n", crop);
        clock = di;
    }

    free(a);
    free(field);
    return 0;
}