#include <iostream> #include <stdio.h> #include <sstream> #include <stdlib.h> using namespace std; long long i,j,n,m,s=0,d,e=0,b,l; long long a[500000+1]; long long p[500000+1]; long long q[500000+1]; long long dd[500000+1]; long long bb[500000+1]; int compare(const void *a,const void *b) { return *(long long *)b - *(long long *)a; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string line; istringstream ss; getline(cin,line); ss.str(line); ss >> n >> m; getline(cin,line); ss.str(line); ss.clear(); i=1; while (ss >> l) { a[i]=l; p[i]=0; q[i]=0; i++; } qsort(&a[1],n,sizeof(long long),compare); for (j=0;j<m;++j) { cin >> dd[j] >> bb[j]; } for (j=0;j<m;++j) { s=0; d=dd[j]; b=bb[j]; for (i=1;i<=n;++i) { long long del=(d-q[i])*a[i]; long long pd=p[i]+del; if (pd >= b){s+=pd-b;p[i]=b;q[i]=d;} else break; } cout <<s<< endl; } return 0; }
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 54 55 56 57 58 59 60 61 62 63 64 | #include <iostream> #include <stdio.h> #include <sstream> #include <stdlib.h> using namespace std; long long i,j,n,m,s=0,d,e=0,b,l; long long a[500000+1]; long long p[500000+1]; long long q[500000+1]; long long dd[500000+1]; long long bb[500000+1]; int compare(const void *a,const void *b) { return *(long long *)b - *(long long *)a; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string line; istringstream ss; getline(cin,line); ss.str(line); ss >> n >> m; getline(cin,line); ss.str(line); ss.clear(); i=1; while (ss >> l) { a[i]=l; p[i]=0; q[i]=0; i++; } qsort(&a[1],n,sizeof(long long),compare); for (j=0;j<m;++j) { cin >> dd[j] >> bb[j]; } for (j=0;j<m;++j) { s=0; d=dd[j]; b=bb[j]; for (i=1;i<=n;++i) { long long del=(d-q[i])*a[i]; long long pd=p[i]+del; if (pd >= b){s+=pd-b;p[i]=b;q[i]=d;} else break; } cout <<s<< endl; } return 0; } |