Pagini recente » Cod sursa (job #32064) | Cod sursa (job #2573784) | Cod sursa (job #892956) | Cod sursa (job #1953314) | Cod sursa (job #154750)
Cod sursa(job #154750)
#include<stdio.h>
FILE*fin=fopen("branza.in","r");
FILE*fout=fopen("branza.out","w");
#define maxn 100001
#define inf 1000000000
#define min(a,b)((a)<(b)?(a):(b))
long long c[maxn],p[maxn],cer[maxn],cerp[maxn],n,s,t,cmin[maxn],deque[maxn],ind[maxn];
int main()
{
int i,st,dr,j;
long long v1,v2;
fscanf(fin,"%lld%lld%lld",&n,&s,&t);
cer[0]=0;cerp[0]=0;
for(i=1;i<=n;i++)
{
fscanf(fin,"%lld%lld",&c[i],&p[i]);
cer[i]=cer[i-1]+p[i];
cerp[i]=cerp[i-1]+p[i]*i;
}
fclose(fin);
st=dr=0;
deque[0]=inf;
ind[0]=0;
cmin[0]=0;
for(i=1;i<=n;i++)
{
if(ind[st]<i-t) st++;
v1=deque[st]-(cerp[n]-cerp[i])*s+(cer[n]-cer[i])*ind[st]*s+(cer[i]-cer[ind[st]])*c[ind[st]];
v2=cmin[i-1]+c[i]*p[i];
cmin[i]=min(v1,v2);
j=dr;
v1=cmin[i]+(cerp[n]-cerp[i])*s-(cer[n]-cer[i])*i*s;
while(deque[j]>v1&&j>=st) j--;
dr=j+1;
deque[dr]=v1;
ind[dr]=i;
}
fprintf(fout,"%lld",cmin[n]);
fclose(fout);
return 0;
}