Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main(){
- long long n, k, c, d;
- cin>>n>>k>>c>>d;
- vector <long long> a(n);
- vector <long long> b(n);
- for (long long i=0; i<n; i++){
- cin>>a[i]>>b[i];
- }
- if (n==1){
- cout<<d*(b[0]-a[0])<<endl;
- return 0;
- }
- vector <long long> dist(n-1);
- for (long long i=0; i<n-1; i++){
- dist[i]=a[i+1]-b[i];
- }
- sort(dist.begin(), dist.end());
- reverse(dist.begin(), dist.end());
- vector <long long> prefix(n-1);
- prefix[0]=dist[0];
- for (long long i=1; i<n-1; i++){
- prefix[i]=prefix[i-1]+dist[i];
- }
- vector <long long> ans(n);
- for (long long i=0; i<n; i++){
- ans[i]+=c*i;
- if ((i+1)*k<2){
- ans[i]+=prefix[n-2]*d;
- continue;
- }
- if ((i+1)*k>=n){
- continue;
- }
- ans[i]+=d*(prefix[n-2]-prefix[(i+1)*k-2]);
- }
- long long minimum=ans[0];
- for (long long i=0; i<n; i++){
- if (ans[i]<minimum){
- minimum=ans[i];
- //cout<<i<<"\n";
- }
- }
- for (long long i=0; i<n; i++){
- minimum+=d*(b[i]-a[i]);
- }
- cout<<minimum<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement