Cod sursa(job #917888)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 18 martie 2013 14:00:33
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<cstdio>
#include<deque>
#define ll long long
#define nmax 100010
using namespace std;
deque<ll>Q;
ll n,s,t,c[nmax],k,sol,i;
int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%lld%lld%lld", &n, &s, &t);
    for(i=1;i<=n;++i)
    {
        scanf("%lld%lld", &c[i], &k);
        for(;Q.size()&&(c[Q.back()]+s*(i-Q.back())>c[i]);Q.pop_back());
        Q.push_back(i);
        if(Q.front()+t<i)Q.pop_front();
        sol+=k*(c[Q.front()]+s*(i-Q.front()));

    }
    printf("%lld", sol);
    return 0;
}