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
#include <iostream>
enum { N_MAX = 500000, M_MAX = 500000 };
typedef unsigned int uint32;
typedef unsigned long long uint64;

uint32 N;

uint32 growth[N_MAX];
uint64 heights[N_MAX];

int main()
{
        uint32 m;
        std::cin >> N >> m;
        for (uint32 i = 0; i < N; i++)
        {
                std::cin >> growth[i];
        }
        uint64 last = 0;
        while (m--)
        {
                uint64 d, b, cut = 0;
                std::cin >> d >> b;

                for (uint32 i = 0; i < N; i++)
                {
                        heights[i] += (d - last) * growth[i];
                        if (heights[i] > b)
                        {
                                cut += heights[i] - b;
                                heights[i] = b;
                        }
                }
                last = d;
                std::cout << cut << std::endl;
        }
}