Cod sursa(job #208289)

Utilizator CezarMocanCezar Mocan CezarMocan Data 15 septembrie 2008 16:58:03
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#include <algorithm>

using namespace std;

long long n,t,s,c[100100],p[100100],m[100100];
long long i,j,l,u,d[100100],lj,rez;

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],&p[i]);
    
l=u=1;
d[1]=1;
m[1]=c[1];

for (i=2;i<=n;i++)
    {
    lj=i-t;
    while ((d[l]<lj)&&(l<=u))
        l++;
        
    while (((c[i]+s*(n-i))<(c[d[u]]+s*(n-d[u])))&&(u>=l))
        u--;
    u++;
    d[u]=i;
    
//    printf("%d %d\n",l,u);
//    for (j=1;j<=n;j++)
//        printf("%d ",d[j]);
//    printf("\n\n");
    
    m[i]=c[d[l]]+s*(n-d[l])-s*(n-i);
    }
    
for (i=1;i<=n;i++)
    rez+=m[i]*p[i];
    
printf("%lld\n",rez);

//for (i=1;i<=n;i++)
//    printf("%d ",m[i]);

return 0;
}