이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
void solve(){
io();
int n;cin>>n;
ll a[n];
for(int i=0;i<n;i++)cin>>a[i];
ll arr[n],brr[n];
arr[0]=brr[n-1]=0;
ll cur=0;
for(int i=1;i<n;i++){
if(a[i]<=a[i-1])cur+=a[i-1]-a[i]+1;
arr[i]=cur;
}
cur=0;
for(int i=n-2;i>=0;i--){
if(a[i]<=a[i+1])cur+=a[i+1]-a[i]+1;
brr[i]=cur;
}
ll ans=min(arr[n-1],brr[0]);
for(int i=0;i<n-1;i++){
ll temp=max(arr[i],brr[i+1]);
ll x=a[i]+arr[i],y=a[i+1]+brr[i+1];
if(y>=x)temp+=y-x+1;
ans=min(ans,temp);
}
cout<<ans<<endl;
}
int main(){
io();
solve();
//int t;cin>>t;for(int i=0;i<t;i++)solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |