fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // https://m...content-available-to-author-only...y.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
  6. struct Slope{
  7.   long long minf;
  8.   priority_queue<long long> L;
  9.   priority_queue<long long,vector<long long>,greater<long long>> R;
  10.  
  11.   // init f(x) = c (const)
  12.   Slope(long long c) : minf(c) {}
  13.  
  14.   // get minimum
  15.   long long get(){ return minf; }
  16.  
  17.   // add c for all
  18.   void add_const(long long c){ minf+=c; }
  19.  
  20.   // add max(0,x-a) (_/)
  21.   void add_xa(long long a){
  22.     if(!L.empty()){minf+=max(0ll,L.top()-a);}
  23.  
  24.     L.push(a);
  25.     R.push(L.top()); L.pop();
  26.   }
  27.  
  28.   // add max(0,a-x) (\_)
  29.   void add_ax(long long a){
  30.     if(!R.empty()){minf+=max(0ll,a-R.top());}
  31.  
  32.     R.push(a);
  33.     L.push(R.top()); R.pop();
  34.   }
  35.  
  36.   // add |x-a| (\/)
  37.   void add_abs(long long a){
  38.     add_xa(a);
  39.     add_ax(a);
  40.   }
  41.  
  42.   // take min(small to large)
  43.   void slmax(){
  44.     while(!R.empty()){R.pop();}
  45.   }
  46.  
  47.   // take min(large to small)
  48.   void lsmax(){
  49.     while(!L.empty()){L.pop();}
  50.   }
  51. };
  52.  
  53. void verify_abc127f(){
  54.   Slope slp(0);
  55.   long long q;
  56.   cin >> q;
  57.  
  58.   while(q>0){
  59.     q--;
  60.     long long typ;
  61.     cin >> typ;
  62.     if(typ==1){
  63.       long long a,b;
  64.       cin >> a >> b;
  65.       slp.add_abs(a);
  66.       slp.add_const(b);
  67.     }
  68.     else{
  69.       cout << slp.L.top() << " ";
  70.       cout << slp.get() << "\n";
  71.     }
  72.   }
  73. }
  74.  
  75. void verify_boj13323(){
  76.   Slope slp(0);
  77.   long long n;
  78.   cin >> n;
  79.   for(long long i=0;i<n;i++){
  80.     long long a;
  81.     cin >> a;
  82.     a-=i;
  83.  
  84.     slp.slmax();
  85.     slp.add_abs(a);
  86.   }
  87.   cout << slp.get() << "\n";
  88. }
  89.  
  90. int main(){
  91.   ios::sync_with_stdio(false);
  92.   cin.tie(nullptr);
  93.  
  94.   // verify_abc127f();
  95.   verify_boj13323();
  96.   return 0;
  97. }
  98.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
7
9 4 8 20 14 15 18
stdout
copy 
13
https://ideone.com/KfZU6X
language:
C++14 (gcc 8.3)
created:
19 days ago
visibility:
secret

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!