#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 200001; const int MAX_D = 1000001; int64_t solutions_per_d[MAX_D]; int64_t t[MAX_N]; int64_t end_of_backing_time[MAX_N]; int64_t solve(int n, int64_t d) { if (solutions_per_d[d] != -1) { return solutions_per_d[d]; } int64_t total_wait_time = 0; end_of_backing_time[0] = max(d, t[0]); total_wait_time += end_of_backing_time[0] - t[0]; for(int i = 1; i < n; i++) { end_of_backing_time[i] = max(end_of_backing_time[i-1] + d, t[i]); total_wait_time += end_of_backing_time[i] - t[i]; } solutions_per_d[d] = total_wait_time; return total_wait_time; } int main() { int n, m; int64_t d; fill_n(solutions_per_d, MAX_D, -1); scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%lld", &t[i]); } for (int i = 0; i < m; i++) { scanf("%lld", &d); printf("%lld\n", solve(n, d)); } 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 | #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 200001; const int MAX_D = 1000001; int64_t solutions_per_d[MAX_D]; int64_t t[MAX_N]; int64_t end_of_backing_time[MAX_N]; int64_t solve(int n, int64_t d) { if (solutions_per_d[d] != -1) { return solutions_per_d[d]; } int64_t total_wait_time = 0; end_of_backing_time[0] = max(d, t[0]); total_wait_time += end_of_backing_time[0] - t[0]; for(int i = 1; i < n; i++) { end_of_backing_time[i] = max(end_of_backing_time[i-1] + d, t[i]); total_wait_time += end_of_backing_time[i] - t[i]; } solutions_per_d[d] = total_wait_time; return total_wait_time; } int main() { int n, m; int64_t d; fill_n(solutions_per_d, MAX_D, -1); scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%lld", &t[i]); } for (int i = 0; i < m; i++) { scanf("%lld", &d); printf("%lld\n", solve(n, d)); } return 0; } |