#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>//i am gay
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define He_he_boy ios_base::sync_with_stdio(0) , cin.tie(0) ,cout.tie(0)
#define ld long double///i like negr a
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define open freopen ("herding.in", "r", stdin);
#define close freopen("herding.out", "w", stdout);
using namespace std;
using namespace __gnu_pbds;
const ll mod = 1e9 + 7;
ll mod_2 = 998244353;
typedef tree<long long, null_type, less_equal<long long> /* � ���������� less_equal<ll> */, rb_tree_tag, tree_order_statistics_node_update>pbds;
ll nok(ll n1, ll n2)
{
return n1 * n2 / __gcd(n1, n2);
}
ll qpow_mod(ll a, ll b, ll md)
{
ll res = 1;
a = a % md;
while (b > 0)
{
if (b & 1)
res = (res * a) % md;
a = (a * a) % md;
b >>= 1;
}
return res;
}
ll pros(ll n) {
if (n == 1) {
return 1;
}
for (ll i = 2; i * i <= n; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
/// --------------------------------------------------------
void Ali(){
ll n;
cin >> n;
ll a[n + 19] = {}, b[n + 19] = {}, c[n + 19] = {};
for(ll i = 1;i <= n;i ++){
cin >> a[i];
b[i] = a[i];
c[i] = a[i];
}
ll dp[n + 19] = {}, dp2[n + 19] = {}, ans[n + 19] = {};
for(ll i = 2;i <= n;i ++){
ans[i] = ans[i - 1];
if(a[i] <= a[i - 1]){
dp[i] = a[i - 1] - a[i] + 1;
a[i] = a[i - 1] + 1;
if(dp[i - 1] > 0){
ans[i] += 1;
}
else{
ans[i] += dp[i];
}
}
}
ll ans2[n + 19] = {};
for(ll i = n - 1;i >= 1;i --){
ans2[i] = ans2[i + 1];
if(b[i + 1] >= b[i]){
dp2[i] = b[i + 1] - b[i] + 1;
b[i] = b[i + 1] + 1;
if(dp2[i + 1] > 0){
ans2[i] ++;
}
else{
ans2[i] += dp2[i];
}
}
}
ll mn = 1e18;
for(ll i = 1;i <= n;i ++){
ll s = max(a[i - 1], b[i + 1]);
if(c[i] <= s){
mn = min(mn, s - c[i] + 1 + max(ans[i - 1], ans2[i + 1]));
}
else{
mn = min(mn, max(ans[i - 1], ans2[i + 1]));
}
}
cout << mn << '\n';
}
/// */* ------------------------------- */*
int main() {
He_he_boy;
ll nigga = 1;
// cin >> nigga;
while(nigga--){
Ali();
}
/*
Are you sure bro ?
*/
}
/// */* ------------------------------- */*
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |