Pagini recente » Cod sursa (job #284783) | Cod sursa (job #1333618) | Cod sursa (job #1008438) | Cod sursa (job #2473144) | Cod sursa (job #1464705)
#include <cstdio>
#include <deque>
#include <vector>
#include <iostream>
using namespace std;
const int MAXREAD = 100000;
vector< pair<int, int> > a;
int N, S, T;
deque<int> Q;
long long cost;
char r[MAXREAD];
int p = MAXREAD - 1;
int x, y, best;
void Read();
void DetCost();
void Get( int& x );
void Next();
int main()
{
freopen( "branza.in", "r", stdin );
freopen( "branza.out", "w", stdout );
Read();
DetCost();
printf( "%lld\n", cost );
fclose(stdin);
fclose(stdout);
return 0;
}
void Read()
{
int i;
Get(N);
Get(S);
Get(T);
a.push_back( make_pair(0, 0) );
for ( i = 1; i <= N; i++ )
{
Get(x);
Get(y);
a.push_back( make_pair(x, y) );
}
a.resize(N + 1);
}
void DetCost()
{
int i;
for ( i = 1; i <= N; i++ )
{
while ( !Q.empty() && i - Q.front() > T )
Q.pop_front();
while ( !Q.empty() && a[i].first < a[Q.back()].first + ( ( i - Q.back() ) * S ) )
Q.pop_back();
Q.push_back(i);
best = ( ( i - Q.front() ) * S ) + a[Q.front()].first;
cost = cost + ( 1LL * best * a[i].second );
}
}
void Get( int& x )
{
for ( ; r[p] < '0' || r[p] > '9'; Next() );
for ( x = 0; r[p] >= '0' && r[p] <= '9'; Next() )
x = ( x * 10 ) + ( r[p] - '0' );
}
void Next()
{
if ( ++p == MAXREAD )
std::fread( r, 1, MAXREAD, stdin ), p = 0;
}