Cod sursa(job #963387)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 17 iunie 2013 12:40:58
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<cstdio>
#define ll long long
const int N=100001;
struct sapt{
    ll c,p;
};
sapt v[N];
ll d[N],s,n,t,i,sapt,nr,c1=1,c2;
int main(){
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%I64d%I64d%I64d",&n,&t,&sapt);
    for(i=1;i<=n;i++)
        scanf("%I64d%I64d",&v[i].c,&v[i].p);
    for(i=1;i<=n;i++){
        if(i>=sapt)
            if(i-d[c1]>sapt)
                c1++;
        while(c2>=c1 && v[i].c<=(v[d[c2]].c)+(i-d[c2])*t)
            c2--;
        d[++c2]=i;
        s+=(v[d[c1]].c+(i-d[c1])*t)*v[i].p;
    }
    printf("%I64d",s);
    return 0;
}