Pagini recente » Cod sursa (job #285476) | Cod sursa (job #2988388) | Cod sursa (job #318902) | Cod sursa (job #2107708) | Cod sursa (job #942560)
Cod sursa(job #942560)
#include<cstdio>
#include<deque>
#define LL long long
#define min(a,b) ((a)<(b)?(a):(b))
FILE *f=fopen("branza.in","r");
FILE *g=fopen("branza.out","w");
using namespace std;
const int NMAX=100005;
struct branza {
int cant;
int cost;
} ;
branza v[NMAX];
LL time,extra,n;
LL bst[NMAX];
deque <int> q;
void Read ( void )
{
fscanf(f,"%lld%lld%lld",&n,&extra,&time);
for(int i(1) ; i <= n ; ++i )
{
fscanf(f,"%d%d",&v[i].cost,&v[i].cant);
}
fclose(f);
}
void Solve ( void )
{
bst[1]=v[1].cant*v[1].cost;
q.push_back(1);
for(int i(2) ; i <= n ; ++i )
{
for ( ;!q.empty() && q.front() < i - time ; q.pop_front() );
for( ; !q.empty() && ( v[i].cost < ( v[q.back()].cost + extra*(i-q.back()) ) ); q.pop_back() );
q.push_back(i);
bst[i]=1LL*min(v[i].cost,(v[q.front()].cost+extra*(i-q.front())))*v[i].cant;
}
}
void Write ( void )
{
LL Answer(0);
for(int i(1) ; i <= n ; ++i )
Answer+=bst[i];
fprintf(g,"%lld",Answer);
fclose(g);
}
int main ( void )
{
Read();
Solve();
Write();
return 0;
}