Pagini recente » Cod sursa (job #1134016) | Cod sursa (job #2078358) | Cod sursa (job #1657386) | Cod sursa (job #2096514) | Cod sursa (job #77145)
Cod sursa(job #77145)
#include<stdio.h>
#include<iostream.h>
#define maxn 128*1024
long long v[maxn*2],poz[maxn],cine[maxn];
long long n,t,s,nr=0,x[maxn],y[maxn];
void schimba(long a,long b)
{
long aux ;
/*aux = v[a];
v[a] = v[b];
v[b] = aux;*/
v[a] = v[b] ^ v[a]^(v[b] = v[a]);
poz[cine[a]] = b;
poz[cine[b]] = a;
cine[a] = cine[a] ^ cine[b] ^ (cine[b] = cine[a]);
}
long urca(long a)
{
while(a>1 && v[a] < v[a/2])
{
schimba(a,a/2);
}
return a;
}
void add(long long a,long b)
{
v[++nr] = a;
cine[nr] = b;
poz[b] = nr;
urca(nr);
}
void coboara(long a)
{
if(a*2>nr) return;
long fav = a*2;
if(a*2+1 <= nr && v[fav] > v[fav+1])
fav = fav+1;
if(v[fav]<v[a])
{
schimba(fav,a);
coboara(fav);
}
}
void scoate(long a)
{
schimba(a,nr);
nr--;
urca(a);
coboara(a);
}
int main()
{
long long sol =0,p;
long long i,a,b;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
//scanf("%lld %lld %lld",&n,&s,&t);
cin>>n>>s>>t;
for(i=1;i<=n;i++)
{
//scanf("%ld %ld",&a,&b);
cin>>a>>b;
if(i>t+1)
scoate(poz[i-t-1]);
add(a+(n-i)*s,i);
p = v[1];
sol += (long long)b *(p-(n-i)*s);
}
long j;
/*for(i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
long long add =0;
long long min = x[i];
for(j=i;j>=i-t&& j>0;add+=s,j--)
{
if(x[j]+add < min)
min = x[j]+add;
}
sol+=min*y[i];
}*/
// printf("%lld",sol);
cout<<sol;
return 0;
}