Pagini recente » Cod sursa (job #1855311) | Cod sursa (job #811870) | Cod sursa (job #2493109) | Cod sursa (job #1502540) | Cod sursa (job #1294267)
#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");
int sum=0 ,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+=v[d[st]]*a[i] + s*(i-d[st]);
}
fprintf(fout ,"%d" ,sum);
return 0;
}