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
51
52
53
#include<iostream>
#include<algorithm>

using namespace std;

int kosz[500000];
int kiedy[500000];
int fast[500000];
int status[500000];

int suma=0;

int n,m;

int main() {
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<n;++i) {
cin>>fast[i];
}
for(int i=0;i<m;++i) {
cin>>kiedy[i]>>kosz[i];
}
sort(fast, fast+n);
int pom;

for(int i=0;i<m;++i) {
suma =0;
for(int j=0;j<n;++j) {
status[j]+=(kiedy[i]-kiedy[i-1])*fast[j];
if(status[j] > kosz[i]) {
suma += status[j]-kosz[i];
status[j]=kosz[i];
}
}
cout<<suma<<"\n";

}

/*

O(nlog(n)+m)) zakladajac ze suma wszystkich dni 
while(mm>=0) {
while(nn >= 0 && kiedy[mm]*fast[nn] > kosz[mm]) {
suma+=kiedy[mm]*fast[nn] - kosz[mm];
--nn;
}
--mm;
}
*/


}