#include <iostream> #include <vector> #include <algorithm> int64_t solve(std::vector<int64_t> const &t, int64_t d) { int64_t r = std::max(d - t[0], 0ll), m = 0; for (int c = 1; c < t.size(); ++c) { m += r; r = std::max(d + r + t[c - 1] - t[c], 0ll); } return m + r; } int main() { std::ios::sync_with_stdio(false); int64_t n, m; std::cin >> n >> m; std::vector<int64_t> t(n); for (int i = 0; i < n; ++i) { std::cin >> t[i]; } int64_t ft = 0; for (int i = 0; i < n; ++i) { ft = std::max(ft, (t[i] + i) / (i + 1)); } int64_t fv = solve(t, ft); int64_t fm = std::numeric_limits<int64_t>::max(); for (int i = 1; i < n; ++i) { fm = std::min(fm, t[i] - t[i - 1]); } for (int i = 0; i < m; ++i) { int64_t d; std::cin >> d; if (d >= ft) { std::cout << (fv + (d - ft) * ((n * (n + 1)) / 2)) << std::endl; } else if (d <= fm) { std::cout << 0 << std::endl; } else { std::cout << solve(t, d) << std::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 | #include <iostream> #include <vector> #include <algorithm> int64_t solve(std::vector<int64_t> const &t, int64_t d) { int64_t r = std::max(d - t[0], 0ll), m = 0; for (int c = 1; c < t.size(); ++c) { m += r; r = std::max(d + r + t[c - 1] - t[c], 0ll); } return m + r; } int main() { std::ios::sync_with_stdio(false); int64_t n, m; std::cin >> n >> m; std::vector<int64_t> t(n); for (int i = 0; i < n; ++i) { std::cin >> t[i]; } int64_t ft = 0; for (int i = 0; i < n; ++i) { ft = std::max(ft, (t[i] + i) / (i + 1)); } int64_t fv = solve(t, ft); int64_t fm = std::numeric_limits<int64_t>::max(); for (int i = 1; i < n; ++i) { fm = std::min(fm, t[i] - t[i - 1]); } for (int i = 0; i < m; ++i) { int64_t d; std::cin >> d; if (d >= ft) { std::cout << (fv + (d - ft) * ((n * (n + 1)) / 2)) << std::endl; } else if (d <= fm) { std::cout << 0 << std::endl; } else { std::cout << solve(t, d) << std::endl; } } return 0; } |