Pagini recente » Cod sursa (job #3210935) | Cod sursa (job #2270437) | Cod sursa (job #37679) | Cod sursa (job #23681) | Cod sursa (job #240315)
Cod sursa(job #240315)
#include <cstdio>
#include <deque>
using namespace std;
#define FIN "branza.in"
#define FOUT "branza.out"
#define NMAX 100100
deque<int> Q;
long long C[NMAX], P[NMAX], M[NMAX], Sol;
int N, S, T;
int main(){
int i,j;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d%d%d", &N, &S, &T);
for (i = 1; i <= N; ++i)
scanf("%d%d", &C[i], &P[i]);
Q.push_back(1);
M[1] = C[1];
for (i = 2; i <= N; ++i){
j = i - T;
while (!Q.empty() && Q.front() < j)
Q.pop_front();
while (!Q.empty() && C[i] + S * (long long)(N - i ) < ( C[ Q.back()] + S * (long long)( N - Q.back() )))
Q.pop_back();
Q.push_back(i);
M[i] = C[ Q.front()] + S * (long long)(N - Q.front()) - S * (long long)(N - i);
}
for (i = 1; i <= N; ++i)
Sol += M[i] * P[i];
printf("%lld\n", Sol);
return 0;
}