Pagini recente » Cod sursa (job #49024) | Cod sursa (job #2842945) | Cod sursa (job #1633456) | Cod sursa (job #2870975) | Cod sursa (job #946935)
Cod sursa(job #946935)
#include <fstream>
#include <deque>
using namespace std;
int main()
{
ifstream cin("branza.in");
ofstream cout("branza.out");
deque <int> coada;
int cost[100005],produs[100005];
int n,s,t,i;
cin>>n>>s>>t;
t++;
for(i=0;i<n;i++)
cin>>cost[i]>>produs[i];
long long int sum=0;
for(i=0;i<n;i++)
{
while(!coada.empty())
if(i-coada.front()>=t)
coada.pop_front();
else
break;
while(!coada.empty())
if((cost[coada.back()]+(s*(unsigned long long int)(i-coada.back())))>=cost[i])
coada.pop_back();
else
break;
coada.push_back(i);
//cout<<(cost[coada.front()]+s*(i-coada.front()))*produs[i]<<endl;
sum+=((cost[coada.front()]+s*(i-coada.front()))*produs[i]);
}
cout<<sum<<'\n';
cin.close();
cout.close();
return 0;
}