đề HSG HN 9 câu 5 =) chúc ae làm đc

Mô tả thuật toán (bài này hay)

Cổ phiếu VNI là cổ phiếu mà có giá trị của n ngày trong đó mỗi giá trị của từng ngày Bình đã biết trước. Vì thế khi ở test 1: Ngày 1 Bình đã mua 1, ngày 2 Bình mua tiếp, đến ngày 3 Bình bán hết để có được lãi, nhận thấy rằng từ ngày đầu tiên khi mua cổ phiếu đầu Bình đã xác định sẽ lãi được 4 đồng, ngày thứ 2 Bình xác định được đã lãi được 3 đồng.........Xem ngày cuối cùng trở về ngày đầu tiên rồi tìm giá trị lớn nhất là Bình sẽ xác định mua khi nào sẽ lời :D. Bây giờ mình chỉ việc sử dụng mảng cộng dồn là giải quyết được bài toán

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 2;
ll n, a[N], s[N], m[N], f[N];
void hand()
{
    m[n] = a[n];
    for(int i = n - 1; i >= 1; --i)
    {
        m[i] = max(a[i], m[i + 1]);
        f[i] = m[i] - a[i];
    }
    for(int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + f[i];
}
int main()
{
    freopen("vni.inp","r",stdin); freopen("vni.out","w",stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    hand();
    int q; cin >> q;
    while(q--)
    {
        int x; cin >> x;
        cout << s[n] - s[x - 1] << "\n";
    }
    return 0;
}