Cod sursa(job #1477424)

Utilizator akaprosAna Kapros akapros Data 26 august 2015 11:15:02
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#define maxN 100002
using namespace std;
int n, m, i, j, t;
long long s, c[maxN], p[maxN];
deque < long long > d;
long long sol;
void read()
{
    freopen("branza.in", "r", stdin);
    scanf("%d %lld %d", &n, &s, &t);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%lld %lld", &c[i], &p[i]);
        while (!d.empty() && (i - d.back()) * s + c[d.back()] >= c[i])
              d.pop_back();
        d.push_back(i);
        if (i - d.front() == t)
            d.pop_front();
        sol = sol + (long long)(((i - d.front()) * s * 1LL + c[d.front()]) * p[i] * 1LL);
    }
}
void print()
{
    freopen("branza.out", "w", stdout);
    printf("%lld", sol);
}
int main()
{
    read();
    print();
    return 0;
}