Pagini recente » Cod sursa (job #2316470) | Cod sursa (job #1201036) | Cod sursa (job #2307425) | Cod sursa (job #406002) | Cod sursa (job #1417626)
#include<fstream>
using namespace std;
int n, i, p, u, t, s;
long long c[100002], P[100002], d[100002], m[100002];
long long sum;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long val(int i){
return c[i] + (n - i) * 1LL * s;
}
int main(){
fin>> n >> s >> t;
for(i = 1; i <= n; i++){
fin>> c[i] >> P[i];
}
m[1] = c[1];
p = u = d[1] = 1;
for(i = 2; i <= n; i++){
m[i] = min(c[i], val(d[p]) - (n - i) * 1LL * s);
while(p <= u && val(d[u]) > val(i)){
u--;
}
u++;
d[u] = i;
if(i - d[p] == t){
p++;
}
}
for(i = 1; i <= n; i++){
sum += m[i] * P[i];
}
fout<< sum <<"\n";
return 0;
}