Pagini recente » Cod sursa (job #2511996) | Cod sursa (job #362373) | Cod sursa (job #2518894) | Cod sursa (job #2467119) | Cod sursa (job #107131)
Cod sursa(job #107131)
#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long
int N, S, T, C[1<<17], P[1<<17];
LL tmp[1<<17], tot_cas[1<<17];
inline LL cost( int x )
{
return ( (LL)N - x ) * (LL)S + C[x];
}
int main()
{
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
int deq[1<<17], fi, la;
scanf("%d %d %d", &N, &S, &T);
for( int i = 1; i <= N; ++i )
scanf("%d %d", C + i, P + i );
deq[ fi = la = 0 ] = 1;
tmp[1] = C[1];
for( int i = 1; i <= N; ++i )
{
while( fi <= la && i - deq[fi] > T )
++fi;
int el = deq[fi];
LL real = cost(el) - ( (LL)N - i ) * (LL)S;
// printf("%d\n", el );
tmp[i] = real;
while( fi <= la && cost( i + 1 ) <= cost( deq[la] ) )
--la;
deq[++la] = i + 1;
}
LL ret = 0;
for( int i = 1; i <= N; ++i )
ret += tmp[i] * P[i];
cout << ret << endl;
return 0;
}