Cod sursa(job #3247806)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 9 octombrie 2024 10:35:21
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <queue>

using namespace std;
using ll = long long;
const int NMAX = 100002;

ifstream cin("branza.in");
ofstream cout("branza.out");

int s;
ll v[NMAX];
deque <int> dq;
int main()
{
    int n, t;
    cin >> n >> s >> t;

    ll cost, cate, ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> cost >> cate;
        v[i] = cost - i * s;

        while(!dq.empty() && v[dq.back()] > v[i])
            dq.pop_back();
        while(!dq.empty() && dq.front() + t < i)
            dq.pop_front();
        dq.push_back(i);

        ans += 1LL * (v[dq.front()] + i * s) * cate;
    }
    cout << ans;
    return 0;
}