mickypinata

JOI: Harvest

Dec 3rd, 2021
697
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 2e5 + 5;
  7.  
  8. int arr[N];
  9. lli qs1[N], qs2[N];
  10.  
  11. int main(){
  12.  
  13.     int n;
  14.     scanf("%d", &n);
  15.     for(int i = 1; i <= n; ++i){
  16.         scanf("%d", &arr[i]);
  17.     }
  18.     for(int i = 1; i <= n; ++i){
  19.         int x = max(0, arr[i - 1] - arr[i] + 1);
  20.         qs1[i] = qs1[i - 1] + x;
  21.     }
  22.     for(int i = n; i >= 1; --i){
  23.         int x = max(0, arr[i + 1] - arr[i] + 1);
  24.         qs2[i] = qs2[i + 1] + x;
  25.     }
  26.     lli mn = 1e18;
  27.     for(int i = 1; i <= n; ++i){
  28.         mn = min(mn, max(qs1[i], qs2[i]));
  29.     }
  30.     cout << mn;
  31.  
  32.     return 0;
  33. }
  34.  
RAW Paste Data