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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 #include using namespace std; typedef long long int LL; #define st first #define nd second #define PII pair const int N = 2e5 + 7; const LL inf = LL(1e18) + 7LL; int n; LL czas[N]; stack > S; priority_queue > Q; int m; LL ans[N]; pair req[N]; LL sum[3]; int licz[N]; LL odl(int u, int v){ return (czas[v] - czas[u] + v - u - 1) / (v - u); } void Union(int u, int v){ sum[1] -= 1LL * licz[v] * czas[v]; sum[2] -= 1LL * licz[v] * (licz[v] - 1) / 2LL; sum[1] -= 1LL * licz[u] * czas[u]; sum[2] -= 1LL * licz[u] * (licz[u] - 1) / 2LL; licz[u] += licz[v]; sum[1] += 1LL * licz[u] * czas[u]; sum[2] += 1LL * licz[u] * (licz[u] - 1) / 2LL; } int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i){ scanf("%lld", &czas[i]); sum[0] += czas[i]; sum[1] += czas[i]; } licz[0] = 1; S.push({0, inf}); for(int i = 1; i <= n; ++i){ LL res = 0LL; while(S.size()){ if(odl(S.top().first, i) < S.top().second){ res = max(res, odl(S.top().first, i)); break; } res = max(res, S.top().second); S.pop(); } Q.push({-res, {S.top().first, i}}); S.push({i, res}); licz[i] = 1; } for(int i = 1; i <= m; ++i){ scanf("%d", &req[i].st); req[i].nd = i; } sort(req + 1, req + m + 1); for(int i = 1; i <= m; ++i){ while(!Q.empty() && -Q.top().first <= req[i].st){ Union(Q.top().nd.st, Q.top().nd.nd); Q.pop(); } ans[req[i].nd] = sum[1] + sum[2] * req[i].st - sum[0]; } for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]); return 0; }