Pagini recente » Cod sursa (job #1083878) | Istoria paginii runda/oni2011_ziua2/clasament | Cod sursa (job #713913) | Cod sursa (job #679329) | Cod sursa (job #942559)
Cod sursa(job #942559)
#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*(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;
}