fork download
copy 
  1. //Onegai no bug
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define task "QG04CHANGE"
  5. #define SZ(c) (c).size()
  6. #define getbit(x,i) (((x) >> (i)) & 1)
  7. #define turnoff(x,i) (x)&(~(1<<(i)))
  8. #define __builtin_popcount __builtin_popcountll
  9. #define all(x) (x).begin(),(x).end()
  10. #define pb(x) push_back(x)
  11. #define eb(x) emplace_back(x)
  12. #define fi first
  13. #define se second
  14. #define For(i,l,r) for(int i = l ; i < r ;i++)
  15. #define Fore(i,l,r) for(int i = l ; i <= r ; i++)
  16. #define Ford(i,l,r) for(int i = l ; i >= r ; i--)
  17. typedef long long ll ;
  18. typedef pair<int,int> ii;
  19. template <class T>
  20. inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
  21. template <class T>
  22. inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
  23. const ll N = 2e5 + 5;
  24. const ll mod =1e16+9;
  25. const ll base = 311;
  26. const int block = 488;
  27. int n,a[N];
  28. ll l[N],r[N];
  29. signed main()
  30. {
  31.     ios_base::sync_with_stdio(0);
  32.     cin.tie(0);cout.tie(0);
  33.     if(fopen(task".inp","r"))
  34.     {
  35.         freopen(task".inp","r",stdin);
  36.         freopen(task".out","w",stdout);
  37.     }
  38.     cin >> n;
  39.     for(int i = 1;  i<= n ; i++)
  40.     {
  41.         cin >> a[i];
  42.     }
  43.     l[0]=0;
  44.     Fore(i,1,n)
  45.     {
  46.         if(a[i-1]  < a[i])l[i]=l[i-1];
  47.         else l[i]=l[i-1]+a[i-1]+1-a[i];
  48.     }
  49.     Ford(i,n,1)
  50.     {
  51.         if(a[i+1]  < a[i])r[i]=r[i+1];
  52.         else r[i]=r[i+1]+a[i+1]+1-a[i];
  53.     }
  54.     ll ans=mod;
  55.     Fore(i,1,n)
  56.     {
  57.         //cout << l[i] << " " << r[i] << endl;
  58.         ans=min(ans,max(l[i],r[i]));
  59.     }
  60.     cout << ans;
  61. }
  62.  
Success #stdin #stdout 0.01s 5424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10000000000000008
https://ideone.com/sVjhXW
language:
C++14 (clang 8.0)
created:
2 years 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!