Pagini recente » Cod sursa (job #613704) | Cod sursa (job #264254) | Cod sursa (job #1356304) | Cod sursa (job #347077) | Cod sursa (job #932763)
Cod sursa(job #932763)
#include<iostream>
#include<fstream>
using namespace std;
#define NMAX 100001
long long d[NMAX], c[NMAX],p[NMAX],deque[NMAX];
inline long long minim(long long a, long long b)
{
if(a<=b)
return a;
return b;
}
int main ()
{
int i,st,dr,n,s,t;
ifstream f("branza.in");
ofstream g("branza.out");
f>>n>>s>>t;
for(i=1;i<=n;i++)
f>>c[i]>>p[i];
f.close();
st=1;
dr=1;
d[1]=c[1]*p[1];
deque[st]=1;
for(i=2;i<=n;i++) {
d[i]=0LL+minim(c[i]*p[i],1LL*s*p[i]*(i-deque[st])+c[deque[st]]*p[i])+d[i-1];
while(st<=dr && c[i]<0LL+c[deque[dr]]+s*(i-deque[dr]))
dr--;
deque[++dr]=i;
if(i-deque[st]+1>t)
st++;
}
g<<d[n];
g.close();
return 0;
}