Pagini recente » Cod sursa (job #2013561) | Rating Luminita Guzovatii (G.Luminita) | Istoria paginii utilizator/iunia_bujita | Cod sursa (job #1134514) | Cod sursa (job #942561)
Cod sursa(job #942561)
#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 {
LL cant;
LL 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,"%lld%lld",&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;
}