이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optmize ("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define spIO ios::sync_with_stdio(false);cin.tie(0)
#define mem(x,va) memset(x,va,sizeof(x))
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
inline ll inv(ll x, ll MOD = mod)
{
ll power = MOD - 2, ret = 1;
while (power)
{
if (power & 1)
(ret *= x) %= MOD;
power >>= 1;
(x *= x) %= MOD;
}
return ret;
}
inline ll gcd(ll x, ll y)
{
if (y == 0) return x;
return gcd(y, x % y);
}
ll pow2(ll target, ll p)
{
ll ret = 1;
while (p)
{
if (p & 1)
(ret *= target) %= mod;
p >>= 1;
(target *= target) %= mod;
}
return ret;
}
int n;
ll arr1[200000 + 5], l[200000 + 5], r[200000 + 5], arr2[200000 + 5];
ll maxx = 0, pl;
int main()
{
spIO;
cin >> n;
for0(i, n) cin >> arr1[i];
for0(i, n) arr2[i] = arr1[i];
ll acc = 0, ans = 0;
l[0] = 0;
for1(i, n - 1)
{
if (arr1[i] + acc <= arr1[i - 1])
{
ll add = arr1[i - 1] - (arr1[i] + acc) + 1;
ans += add;
acc += add;
arr1[i] += acc;
}
else
acc = 0;
l[i] = ans;
//cout << ans << '\n';
}
acc = 0;
r[n - 1] = 0;
ans = 0;
for (int i = n - 2; i >= 0; i--)
{
if (arr2[i] + acc <= arr2[i + 1])
{
ll add = arr2[i + 1] - (arr2[i] + acc) + 1;
ans += add;
acc += add;
arr2[i] += acc;
//cout << ans << ' ' << acc << ' ' << arr[i] << '\n';
}
else
acc = 0;
r[i] = ans;
//cout << ans << ' ' << acc << '\n';
}
ll fans = 2e18;
for0(i, n)
{
fans = min(fans, max(l[i], r[i]));
}
//for0(i, n) cout << l[i] << ' '; cout << '\n';
//for0(i, n) cout << r[i] << ' '; cout << '\n';
cout << fans << '\n';
}
/*
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
1 | #pragma GCC optmize ("O3,unroll-loops")
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |