Pagini recente » Cod sursa (job #2187003) | Cod sursa (job #2886607) | Cod sursa (job #2887326) | Cod sursa (job #2107063) | Cod sursa (job #1814712)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
struct branza
{
long c, p;
}sapt[100005];
long n, s, t;
long long costMinim;
deque <long> q;
void citire()
{
scanf("%d%d%d", &n, &s, &t);
for(int i=1; i<=n; ++i)
scanf("%d%d", &sapt[i].c, &sapt[i].p);
}
int ok(int j, int i)
{
if(((i-j)*s+sapt[j].c)*sapt[i].p<sapt[i].c*sapt[i].p)
return 0;
return 1;
}
void rezolvare()
{
q.push_back(1);
costMinim=sapt[1].c*sapt[1].p;
for(int i=2; i<=n; ++i)
{
while(!q.empty()&& ok(q.back(),i)==1)
q.pop_back();
q.push_back(i);
while(!q.empty()&&(i-q.front()>t))
q.pop_front();
int j=q.front();
costMinim+=((i-j)*s+sapt[j].c)*sapt[i].p;
}
}
int main()
{
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
citire();
rezolvare();
printf("%lld", costMinim);
return 0;
}