Pagini recente » Cod sursa (job #23677) | Cod sursa (job #3120844) | Cod sursa (job #1017579) | Cod sursa (job #2271650) | Cod sursa (job #1304750)
#include <stdio.h>
FILE *fin ,*fout;
#define N 100001
int st=1 ,dr=0 , d[N] , v[N] ,a[N] ,n ,k ,s;
void stanga (int i)
{
if(i-d[st]==k)
{
st++;
}
}
void dreapta (int i)
{
while(st<=dr && v[i]<=v[d[dr]]+ s*(i-d[dr]))
{
dr--;
}
d[++dr]=i;
}
int main()
{
fin = fopen("branza.in" ,"r");
fout= fopen("branza.out" ,"w");
long long sum=0;
int i;
fscanf(fin ,"%d%d%d" ,&n ,&s ,&k);
for(i=1;i<=n;i++)
{
fscanf(fin ,"%d%d" ,&v[i] ,&a[i]);
}
for(i=1;i<=n;i++)
{
stanga(i);
dreapta(i);
sum+=(long long)(v[d[st]] + s*(i-d[st]))*a[i];
}
fprintf(fout ,"%lld" ,sum);
return 0;
}