Pagini recente » Cod sursa (job #2425795) | Cod sursa (job #1024955) | Cod sursa (job #168512) | Cod sursa (job #2674547) | Cod sursa (job #755189)
Cod sursa(job #755189)
#include<fstream>
#include<deque>
#include<algorithm>
#define dim 100007
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int s,i,n,c[dim],p[dim],b[dim],v[dim],minu[dim],in,sf,t,cm;
long long cost;
long long min(long long a,long long b){
if(a<b)
return a;
return b;
}
int main (){
f>>n>>s>>t;
cost=0;
for (i=1;i<=n;++i){
f>>c[i]>>p[i];
b[i]=c[i]+s*(n-i);
}
in=1;
sf=0;
for (i=1;i<=n;i++){
while(in<=sf && b[i]<b[v[sf]])
sf--;
v[++sf]=i;
while(v[in]<i-t)
in++;
minu[i]=v[in];
}
for(i=1;i<=n;i++)
cost=cost+(long long )p[i]*(c[minu[i]]+(i-minu[i])*s);
g<<cost<<"\n";
return 0;
}