Pagini recente » Cod sursa (job #940366) | Cod sursa (job #2215460) | Cod sursa (job #2891021) | Cod sursa (job #2690478) | Cod sursa (job #1809211)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
FILE *f=fopen("branza.in","r");
FILE *f1=fopen("branza.out","w");
long long c[100010],p[100010],n,s,t;
long long sum;
deque <long> q;
void citire( )
{
fscanf(f,"%d%d%d",&n,&s,&t);
for(int i=1;i<=n;i++)
fscanf(f,"%d%d",&c[i],&p[i]);
}
int good(int j,int i)
{
if(((i-j)*s+c[j])*p[i]<c[i]*p[i])
return 0;
return 1;
}
void add(int i)
{
while(!q.empty()&&good(q.back(),i)==1)
q.pop_back();
q.push_back(i);
}
void eraser(int i)
{
while(!q.empty()&&(i-q.front()+1>t))
q.pop_front();
}
void rez( )
{
q.push_back(1);
sum=c[1]*p[1];
for(int i=2;i<=n;i++)
{
add(i);
eraser(i);
int j=q.front();
sum+=((i-j)*s+c[j])*p[i];
}
}
int main()
{
citire();
rez( );
fprintf(f1,"%lld",sum);
return 0;
}