Pagini recente » Cod sursa (job #2457125) | Cod sursa (job #315757) | Cod sursa (job #2593204) | Cod sursa (job #1126097) | Cod sursa (job #2456638)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>
using namespace std;
const long long NMax = (long long)1e5+10;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long C[NMax], P[NMax];
deque < long long > dq;
bool betterPrice(long long i, long long j, long long S){
if(S * (i-j) + C[j] >= C[i]){
return true;
}
return false;
}
int main()
{
long long N, S, T; fin >> N >> S >> T;
for(long long i=1; i<=N; i++){
fin >> C[i] >> P[i];
}
long long sum = C[1] * P[1];
dq.push_back(1);
for(long long i=2; i<=N; i++){
if(i - dq.front() > T){
dq.pop_front();
}
while(!dq.empty() && betterPrice(i, dq.back(), S)){
dq.pop_back();
}
dq.push_back(i);
sum += 1LL * C[dq.front()] * P[i] + P[i] * (i - dq.front()) * S;
}
fout << sum;
return 0;
}