Pagini recente » Cod sursa (job #2489944) | Cod sursa (job #1584768) | Cod sursa (job #708927) | Cod sursa (job #2246046) | Cod sursa (job #382181)
Cod sursa(job #382181)
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int c[1<<17],p[1<<17],dq[1<<17];
int n,s,t,i,st=1,dr=0;
inline void stanga(int i){
if(i-t>0 && dq[st]==i-t){
st++;
}
}
void dreapta(int i){
while ( st<=dr && c[i]<=c[dq[dr]]+s*(i-dq[dr])){
dr--;
}
dq[++dr]=i;
}
int main(){
in>>n>>s>>t;
long long sum=0;
for(i=1;i<=n;i++){
in>>c[i]>>p[i];
}
for(i=1;i<=n;i++){
stanga(i);
dreapta(i);
sum=sum+p[i]*(c[dq[st]]+s*(i-dq[st]));
}
out<<sum;
in.close();
out.close();
return 0;
}