Pagini recente » Cod sursa (job #578186) | Cod sursa (job #1921358) | Cod sursa (job #2716881) | Cod sursa (job #2263530) | Cod sursa (job #1304752)
#include <stdio.h>
FILE *fin ,*fout;
#define N 1<<17
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;
}