Pagini recente » Cod sursa (job #2248103) | Cod sursa (job #875551) | Cod sursa (job #1525796) | Cod sursa (job #1064393) | Cod sursa (job #932759)
Cod sursa(job #932759)
#include<iostream>
#include<fstream>
using namespace std;
#define NMAX 100001
int c[NMAX],p[NMAX],deque[NMAX];
long long d[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],s*p[i]*(i-deque[st])+c[deque[st]]*p[i])+d[i-1];
while(st<=dr && c[i]<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;
}