Pagini recente » Profil PaNa | Monitorul de evaluare | Profil LunguAlexandru | Istoria paginii utilizator/dydy | Cod sursa (job #1419076)
#include<fstream>
#define f first
#define s second
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int d[100005];
unsigned long long c,u,p,k,i,n,cost;
pair<int,int> v[100005];
int main(){
fin>>n>>c>>k;
for(i=1;i<=n;i++){
fin>>v[i].first>>v[i].second;
}
d[1]=p=u=1;
cost=v[1].f*v[1].s;
for(i=2;i<=n;i++){
while(p<=u && v[d[u]].f+(i-d[u])*c*1LL > v[i].f){
u--;
}
d[++u]=i;
if(i-d[u]==k+1){
p++;
}
cost+=(v[d[p]].f+(i-d[p])*c)*v[i].s*1LL;
}
fout<<cost;
return 0;
}