Pagini recente » Cod sursa (job #406738) | Istoria paginii runda/no_commies_aloud | Cod sursa (job #336880) | Cod sursa (job #2563374) | Cod sursa (job #1503204)
#include <fstream>
#include <deque>
using namespace std;
const int NMAX= 100000;
ifstream in( "branza.in" );
ofstream out( "branza.out" );
deque <int> d;
int cost[NMAX+1], cant[NMAX+1];
int main( )
{
int N, S, T;
in >> N >> S >> T;
for( int i= 1; i<=N; ++i )
{
in >> cost[i] >> cant[i];
}
int 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;
}