Cod sursa(job #1667407)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 28 martie 2016 21:56:22
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int Mn = 1e5 + 6;

int n, t, s;
int c[Mn], p[Mn];
long long ans;
deque< int > dq;

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);

    scanf("%d %d %d", &n, &s, &t);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &c[i], &p[i]);
        while (!dq.empty() && c[i] <= c[dq.back()] + s * (i - dq.back()))
              dq.pop_back();

        dq.push_back(i);
        if (i - dq.front() > t)
           dq.pop_front();

        ans += 1LL * p[i] * (1LL * c[dq.front()] + 1LL * s * (i - dq.front()));
    }

    printf("%lld\n", ans);

  return 0;
}