// O(n*m) ;_; // zawiodlem wszystkich #include <cstdio> #define MAKS 500010 using namespace std; typedef long long int lld; int a[MAKS]; lld v[MAKS]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&a[i]); lld akt=0; for(int i=0;i<m;i++) { lld d,b; scanf("%lld %lld",&d,&b); for(int j=0;j<n;j++)v[j]+=a[j]*(d-akt); akt=d; lld wyn=0; for(int j=0;j<n;j++) { if(v[j]>=b) { wyn+=v[j]-b; v[j]=b; } } printf("%lld\n",wyn); } }
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 | // O(n*m) ;_; // zawiodlem wszystkich #include <cstdio> #define MAKS 500010 using namespace std; typedef long long int lld; int a[MAKS]; lld v[MAKS]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&a[i]); lld akt=0; for(int i=0;i<m;i++) { lld d,b; scanf("%lld %lld",&d,&b); for(int j=0;j<n;j++)v[j]+=a[j]*(d-akt); akt=d; lld wyn=0; for(int j=0;j<n;j++) { if(v[j]>=b) { wyn+=v[j]-b; v[j]=b; } } printf("%lld\n",wyn); } } |