Pagini recente » Cod sursa (job #1756956) | Cod sursa (job #1122848) | Cod sursa (job #1040773) | Cod sursa (job #539954) | Cod sursa (job #2456637)
#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");
int C[NMax], P[NMax];
deque < int > dq;
bool betterPrice(int i, int j, int S){
if(S * (i-j) + C[j] >= C[i]){
return true;
}
return false;
}
int main()
{
int N, S, T; fin >> N >> S >> T;
for(int i=1; i<=N; i++){
fin >> C[i] >> P[i];
}
long long sum = C[1] * P[1];
dq.push_back(1);
for(int 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;
}