Pagini recente » Cod sursa (job #277865) | Cod sursa (job #774456) | Cod sursa (job #470057) | Cod sursa (job #2675046) | Cod sursa (job #1503205)
#include <fstream>
#include <deque>
using namespace std;
const int NMAX= 100000;
ifstream in( "branza.in" );
ofstream out( "branza.out" );
deque <long long> d;
long long cost[NMAX+1], cant[NMAX+1];
int main( )
{
long long N, S, T;
in >> N >> S >> T;
for( int i= 1; i<=N; ++i )
{
in >> cost[i] >> cant[i];
}
long long Ans = 0;
d.push_back( 1 );
Ans += cant[1]*cost[1];
for( int i= 2; i<=N; ++i )
{
while( !d.empty() && cost[i]<cost[ d.back() ] + S*( i-d.back( ) ) )
{
d.pop_back( );
}
d.push_back( i );
while( i-d.front() > T )
{
d.pop_front();
}
Ans += cost[ d.front() ] * cant[i] + cant[i]*S*( i-d.front() );
}
out << Ans << '\n';
return 0;
}