Advertisement
ekzolot

Untitled

Nov 3rd, 2022
576
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int main(){
  6.     long long n, k, c, d;
  7.     cin>>n>>k>>c>>d;
  8.     vector <long long> a(n);
  9.     vector <long long> b(n);
  10.     for (long long i=0; i<n; i++){
  11.         cin>>a[i]>>b[i];
  12.     }
  13.     if (n==1){
  14.         cout<<d*(b[0]-a[0])<<endl;
  15.         return 0;
  16.     }
  17.     vector <long long> dist(n-1);
  18.     for (long long i=0; i<n-1; i++){
  19.         dist[i]=a[i+1]-b[i];
  20.     }
  21.     sort(dist.begin(), dist.end());
  22.     reverse(dist.begin(), dist.end());
  23.     vector <long long> prefix(n-1);
  24.     prefix[0]=dist[0];
  25.     for (long long i=1; i<n-1; i++){
  26.         prefix[i]=prefix[i-1]+dist[i];
  27.     }
  28.     vector <long long> ans(n);
  29.     for (long long i=0; i<n; i++){
  30.         ans[i]+=c*i;
  31.         if ((i+1)*k<2){
  32.             ans[i]+=prefix[n-2]*d;
  33.             continue;
  34.         }
  35.         if ((i+1)*k>=n){
  36.             continue;
  37.         }
  38.         ans[i]+=d*(prefix[n-2]-prefix[(i+1)*k-2]);
  39.     }
  40.     long long minimum=ans[0];
  41.     for (long long i=0; i<n; i++){
  42.         if (ans[i]<minimum){
  43.             minimum=ans[i];
  44.             //cout<<i<<"\n";
  45.         }
  46.     }
  47.     for (long long i=0; i<n; i++){
  48.         minimum+=d*(b[i]-a[i]);
  49.     }
  50.     cout<<minimum<<endl;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement