Cod sursa(job #2006769)

Utilizator victoreVictor Popa victore Data 31 iulie 2017 16:49:10
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<cstdio>
#include<deque>

using namespace std;

const int nmax=1e5+5;

deque<int> indmin;
int c[nmax],p;
long long sol;

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    int n,i,j,s,t;
    scanf("%d%d%d",&n,&s,&t);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&c[i],&p);
        c[i]-=i*s;
        while(!indmin.empty() && i-indmin.front() >t)
            indmin.pop_front();
        while(!indmin.empty() && c[indmin.back()] > c[i])
            indmin.pop_back();
        indmin.push_back(i);
        sol = sol+ (1LL*c[indmin.front()] + i*s)*p;
    }
    printf("%lld",sol);
}