Pagini recente » Cod sursa (job #841123) | Cod sursa (job #1704796) | Cod sursa (job #1529849) | Cod sursa (job #321033) | Cod sursa (job #155305)
Cod sursa(job #155305)
#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 rez,c[maxn],p[maxn];
int main()
{
int i,j,n,s,t,st,dr;
long long v1,v2,deque[maxn],ind[maxn];
fscanf(fin,"%d%d%d",&n,&s,&t);
for(i=1;i<=n;i++)
fscanf(fin,"%lld%lld",&c[i],&p[i]);
fclose(fin);
st=dr=0;
deque[0]=inf;
ind[0]=0;
rez=0;
for(i=1;i<=n;i++)
{
if(ind[st]<i-t) st++;
v1=p[i]*(deque[st]-(n-i)*s);
v2=c[i]*p[i];
rez+=min(v1,v2);
v1=c[i]+(n-i)*s;
j=dr;
while(v1<deque[j]&&j>=st) j--;
dr=j+1;
deque[dr]=v1;
ind[dr]=i;
}
fprintf(fout,"%lld",rez);
fclose(fout);
return 0;
}