// Lupus Nocawy 22 XI 2017, PA2017 // http://potyczki.mimuw.edu.pl/ // Runda 2 // Zadanie: ZAP // Zapiekanki 2 [B] #include <cstdio> #include <algorithm> #include <vector> using namespace std; #define REP(i,n) for(int i=0, _n=n; i<_n; ++i) #define FOR(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i) #define FORD(i,a,b) for(int i=(a), _b=(b); i>=_b; --i) #define IT(i,x) __typeof__(x) i=x #define FOREACH(it,x) for(__typeof__((x).begin()) it=(x).begin(); it!=(x).end(); ++it) #define ALL(x) x.begin(),x.end() #define MP make_pair #define PB push_back #define DEBUG(x) if(debug) cout << x << endl; typedef long long int lli; const int max_n = 200000; const int max_m = 200000; const lli max_t = 1000000000000; //10^12 const int max_d = 1000000; //10^6 lli t[max_n+1]; int d[max_m+1]; lli s[max_n+1]; // tablica sum czesciowych t[0]+...+t[i] int main(void){ int n,m; scanf("%d %d", &n, &m); FOR(i,1,n) scanf("%lli ", t+i); // FOR(i,0,n) printf("%lld ", t[i]); printf("\n"); FOR(i,1,m) scanf("%d ", d+i); // FORD(i,n,1) // t[i] = t[i]-t[i-1]; // FOR(i,0,n) printf("%lld ", t[i]); printf("\n"); // sort(t,t+n+1); // FOR(i,0,n) printf("%lld ", t[i]); printf("\n"); // FOR(i,1,n) // s[i] = s[i-1]+t[i]; // FOR(i,0,n) printf("%lld ", s[i]); printf("\n"); FOR(j,1,m){ //int k = n; //while(d[j]<t[k]) k--; // int k = lower_bound(t,t+n+1, d[j]) - t - 1; // printf("%d\n", k); // lli r = d[j] * k - s[k]; lli r = 0; lli e = 0; FOR(i,1,n){ e = max(e+d[j], t[i]); r += e-t[i]; } printf("%lli\n", r); } return 0; } // 0 24 27 40 42 50 67 68 80 85 86 // 0 24 33 42 51 60 69 78 87 96 105 // 0 0 6 2 9 10 2 10 9 9 19
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 65 66 67 68 | // Lupus Nocawy 22 XI 2017, PA2017 // http://potyczki.mimuw.edu.pl/ // Runda 2 // Zadanie: ZAP // Zapiekanki 2 [B] #include <cstdio> #include <algorithm> #include <vector> using namespace std; #define REP(i,n) for(int i=0, _n=n; i<_n; ++i) #define FOR(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i) #define FORD(i,a,b) for(int i=(a), _b=(b); i>=_b; --i) #define IT(i,x) __typeof__(x) i=x #define FOREACH(it,x) for(__typeof__((x).begin()) it=(x).begin(); it!=(x).end(); ++it) #define ALL(x) x.begin(),x.end() #define MP make_pair #define PB push_back #define DEBUG(x) if(debug) cout << x << endl; typedef long long int lli; const int max_n = 200000; const int max_m = 200000; const lli max_t = 1000000000000; //10^12 const int max_d = 1000000; //10^6 lli t[max_n+1]; int d[max_m+1]; lli s[max_n+1]; // tablica sum czesciowych t[0]+...+t[i] int main(void){ int n,m; scanf("%d %d", &n, &m); FOR(i,1,n) scanf("%lli ", t+i); // FOR(i,0,n) printf("%lld ", t[i]); printf("\n"); FOR(i,1,m) scanf("%d ", d+i); // FORD(i,n,1) // t[i] = t[i]-t[i-1]; // FOR(i,0,n) printf("%lld ", t[i]); printf("\n"); // sort(t,t+n+1); // FOR(i,0,n) printf("%lld ", t[i]); printf("\n"); // FOR(i,1,n) // s[i] = s[i-1]+t[i]; // FOR(i,0,n) printf("%lld ", s[i]); printf("\n"); FOR(j,1,m){ //int k = n; //while(d[j]<t[k]) k--; // int k = lower_bound(t,t+n+1, d[j]) - t - 1; // printf("%d\n", k); // lli r = d[j] * k - s[k]; lli r = 0; lli e = 0; FOR(i,1,n){ e = max(e+d[j], t[i]); r += e-t[i]; } printf("%lli\n", r); } return 0; } // 0 24 27 40 42 50 67 68 80 85 86 // 0 24 33 42 51 60 69 78 87 96 105 // 0 0 6 2 9 10 2 10 9 9 19 |