Cod sursa(job #2096237)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 28 decembrie 2017 20:33:26
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 1e5;

int n, t, s;
int c[NMAX + 2], p[NMAX + 2];

deque<int> dq;
long long ans;
long long sapt[NMAX + 2];

int main()
{
    in >> n >> s >> t;

    for(int i = 1; i <= n; i++)
    {
        in >> c[i] >> p[i];
        while(!dq.empty() && dq.front() < i - t)
            dq.pop_front();
        while(!dq.empty() && c[dq.back()] +  s * (n - dq.back()) >= c[i] + s * (n - i))
            dq.pop_back();

        dq.push_back(i);

        sapt[i] = c[dq.front()] + s * (n - dq.front()) - s * (n - i);
    }

    for(int i = 1; i <= n; i++)
        ans += 1LL * p[i] * sapt[i];

    out << ans << '\n';

    return 0;
}