fork download
copy 
  1. ///Link: https://h...content-available-to-author-only...u.vn/contest/26lqpt10 - NOAI&NOCHEAT@LqPT26
  2. ///Author: NHB_0xCKT
  3. #include <bits/stdc++.h>
  4. #define ll long long
  5. #define F first
  6. #define S second
  7. #define NAME ""
  8. using namespace std;
  9. const int MM = 1e6+5;
  10. ll a[MM],n,s;
  11. namespace solve1{
  12.     ll dp[1005][1005];
  13.     void sol(){
  14.         for(int i = 0;i<=n;i++){
  15.             for(int j = 0;j<=n;j++){
  16.                 dp[i][j] = LLONG_MIN;
  17.             }
  18.         }
  19.         dp[0][0] = 0;
  20.         for(int i = 1;i<=n;i++){
  21.             for(int j = 0;j<=i;j++){
  22.                 if(dp[i-1][j] != LLONG_MIN) dp[i][j] = dp[i-1][j] - s*j;
  23.                 if(j>0 && dp[i-1][j-1] != LLONG_MIN) dp[i][j] = max(dp[i][j],dp[i-1][j-1] - s*(j-1) - a[i]);
  24.                 if(j<i && dp[i-1][j+1] != LLONG_MIN) dp[i][j] = max(dp[i][j],dp[i-1][j+1] - s*(j+1) + a[i]);
  25.             }
  26.         }
  27.         cout<<dp[n][0];
  28.     }
  29. }
  30. namespace solve2{
  31.     ll ans = 0, cnt = 0;
  32.     void sol(){
  33.         priority_queue<ll,vector<ll>,greater<ll>>pq;
  34.         for(int i = 1;i<=n;i++){
  35.             ll val = a[i] - s*i;
  36.             if(!pq.empty() && pq.top() <val){
  37.                 ans += val - pq.top();
  38.                 pq.pop();
  39.                 pq.push(val);
  40.             }
  41.             pq.push(val);
  42. //            cout<<val<<"\n";
  43. //            cout<<i<<" "<<ans<<"\n";
  44.         }
  45.         cout<<ans<<"\n";
  46.     }
  47. }
  48. int main(){
  49. //    freopen(NAME".inp","r",stdin);
  50. //    freopen(NAME".out","w",stdout);
  51.     ios::sync_with_stdio(0);
  52.     cin.tie(0);
  53.     cin>>n>>s;
  54.     for(int i = 1;i<=n;i++) cin>>a[i];
  55.     solve2::sol();
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/U3Pgie
language:
C++14 (gcc 8.3)
created:
6 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!