Pagini recente » Cod sursa (job #3316626) | Cod sursa (job #3301237) | Cod sursa (job #3300955) | Cod sursa (job #3338176) | Cod sursa (job #3308697)
#include <fstream>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include <vector>
#define int long long
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
deque<int> dq;
int n, s, t, dp[100005];
pair<int, int> v[100005];
signed main(){
cin>>n>>s>>t;
for (int i = 1; i <= n; i++){
cin>>v[i].first>>v[i].second;
while (!dq.empty() && v[dq.back()].first - s * dq.back() > v[i].first - s * i){
dq.pop_back();
}
while (!dq.empty() && dq.front() <= i - t - 1){
dq.pop_front();
}
dq.push_back(i);
dp[i] = dp[i - 1] + v[i].second * (v[dq.front()].first - s * dq.front() + s * i);
}
cout<<dp[n];
}