Pagini recente » Cod sursa (job #111972) | Cod sursa (job #1157346) | Cod sursa (job #872315) | Cod sursa (job #2542037) | Cod sursa (job #1138699)
#include <fstream>
#include <deque>
using namespace std;
const int nmax=100000;
long long co[nmax+1], ca[nmax+1];
ifstream in("branza.in");
ofstream out("branza.out");
deque <long long> deq;
int main()
{
int n, s, t;
in >> n >> s >> t;
for( int i=0; i<n; ++i )
{
in >> co[i] >> ca[i];
}
long long suma = 0;
deq.push_back( 0 );
suma += ca[0]*co[0];
for( int i=1; i<n; i++)
{
while(!deq.empty() && co[i] < co[ deq.back() ]+s*( i-deq.back( ) ) )
{
deq.pop_back( );
}
deq.push_back( i );
while( i-deq.front() > t ) {
deq.pop_front();
}
suma += co[ deq.front() ] * ca[i] + ca[i]*s*( i-deq.front() );
}
out << suma << '\n';
return 0;
}