fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e6)+7;
  14.  
  15. int n;
  16. ll s , a[maxN];
  17.  
  18. void solve(){
  19.     cin >> n >> s;
  20.     for (int i = 1 ; i <= n ; i++){
  21.         cin >> a[i];
  22.         a[i] -= 1ll * i * s;
  23.     }
  24.     priority_queue<ll , vector<ll> , greater<ll>> pq;
  25.     ll ans = 0;
  26.     for (int i = 1 ; i <= n ; i++){
  27.         if (pq.empty() == 0 && pq.top() < a[i]){
  28.             ans += 1ll * a[i] - pq.top();
  29.             pq.pop();
  30.             pq.push(a[i]);
  31.         }
  32.         pq.push(a[i]);
  33.     }
  34.     cout << ans << "\n";
  35. }
  36.  
  37. #define name "A"
  38.  
  39. int main(){
  40.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  41.     if (fopen(name".INP" , "r")){
  42.         freopen(name".INP" , "r" , stdin);
  43.         freopen(name".OUT" , "w" , stdout);
  44.     }
  45.     int t = 1; //cin >> t;
  46.     while (t--) solve();
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/cvObMU
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!