이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, ans = 1e18; cin >> n;
int a[n];
for(int &i : a) cin >> i;
array<int, 2> dp0[n], dp1[n];
dp0[0] = {0, a[0]}; // cost, ending
dp1[n-1] = {0, a[n-1]};
for(int i=1; i<n; ++i){
int x = dp0[i-1][0], y = dp0[i-1][1];
if(y < a[i] + x) dp0[i] = {x, a[i]+x};
else dp0[i] = {x + y + 1LL - (a[i]+x), y + 1LL};
x = dp1[n-i][0], y = dp1[n-i][1];
if(a[n-i-1] + x > y) dp1[n-i-1] = {x, a[n-i-1] + x};
else dp1[n-i-1] = {x + y + 1LL - (a[n-i-1]+x), y + 1LL};
}
for(int i=0; i<n; ++i){
// cout << a[i] sp dp0[i][0] sp dp0[i][1] nl;
ans = min(ans, max(dp0[i][0], dp1[i][0]));
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |