Pagini recente » Cod sursa (job #2802195) | Cod sursa (job #1833598) | Cod sursa (job #2700423) | Cod sursa (job #3135907) | Cod sursa (job #2378370)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
deque<long long>d;
long long N,S,T,pozi,i,C[100005],sum,P;
int main()
{
//citire
fin>>N>>S>>T;
//punem in capatul dequelui toate variantele si, la introducerea alteia noi, le scoatem pe cele mai putin eficiente ca aceasta;
//in fata vom avea mereu cea mai buna varianta;
//nu uitam sa scoatem cele mai vechi de T
for(i=1;i<=N;i++){
fin>>C[i]>>P;
while(!d.empty() && (C[d.back()] + S*(i-d.back()) > C[i])) d.pop_back();
d.push_back(i);
while(i-d.front() > T && !d.empty()) d.pop_front();
sum+=(C[d.front()]+S*(i-d.front()))*P;
}
fout<<sum;
return 0;
}