# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1010520 | vjudge1 | Growing Vegetables is Fun 4 (JOI21_ho_t1) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bitsstdc++.h"
typedef long long ll;
using namespace std;
//#define int long long
ll f1(ll d){
if(d > 0) return 0;
else return 1-d;
}
ll f2(ll d){
if(d < 0) return 0;
else return d+1;
}
signed main(){
ll n;
cin >> n;
ll a[n];
ll maxx = 0;
ll d[n];
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < n-1; i++){
d[i] = a[i+1] - a[i];
// cout << d[i] << " ";
}
// cout << endl;
ll p[n+1], s[n+1];
p[0] = 0; s[0] = 0;
for(int i = 1; i < n; i++){
p[i] = p[i-1]+f1(d[i-1]);
s[i] = s[i-1]+f2(d[n-i-1]);
// cout << p[i-1] << " " << s[i-1] << endl;;
}
// cout << p[n-1] << " " << s[n-1] << endl << "/";
ll ans = LLONG_MAX;
for(int i = 0; i < n; i++){
ans = min(ans, maxx = max(p[i], s[n-i-1]));
// cout << p[i] << " " << s[n-i-1] << " " << ans << endl;
}
cout << ans;
}