이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_[1]t;
//// order_of_key(k) : ���������� ���������� ���������, ������� ������ ������ ������ �������� k �� ����� O(logn).
//// find_by_order(k) : ���������� �������� � k-�� �������� (������ �� ����) � ������ �� ����� O(logn).
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define str string
#define ld long double
#define fi first
#define pb push_back
#define pf push_front
#define se second
#define all(a) a.begin() , a.end()
#define run_vasya_run ios_base::sync_with_stdio(0) , cin.tie(0) ,cout.tie(0)
#define ull unsigned long long
#define open freopen ("cereal.in", "r", stdin);
#define close freopen("cereal.out", "w", stdout);
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> order_set;
const ll mod = 998244353;
const ll N = 1e6 + 100;
ll lcm(ll a, ll b)
{
return (a * b) / __gcd(a, b);
}
ll binpow(ll a, ll n)
{
if(n < 1)
{
return 1;
}
if(n == 1)
{
return a % mod;
}
ll b = binpow(a, n / 2);
b = (b * b) % mod;
if(n % 2 == 1)
{
b = (b * a) % mod;
}
return b % mod;
}
main()
{
run_vasya_run;
//open ; close;
///kam kam podgon
ll _;
_ = 1;
//cin >> _;
while(_ --)
{
ll n , answer , kol;
cin >> n;
pair<ll,ll>dp[n + 18] , dp1[n + 19];
ll a[n + 18] , b[n + 19];
for(int i = 1;i <= n;i ++)
{
cin >> a[i];
b[i] = a[i];
}
for(int i = 0;i <= n + 10;i ++)
{
dp[i].fi = 0;
dp1[i].fi = 0;
dp[i].se = 0;
dp1[i].se = 0;
}
dp[1].fi = 0;
dp[1].se = a[1];
for(int i = 2;i <= n;i ++)
{
dp[i].fi = dp[i - 1].fi;
if(a[i] <= a[i - 1])
{
dp[i].fi += (a[i - 1] + 1 - a[i]);
a[i] += (a[i - 1] + 1 - a[i]);
}
dp[i].se = a[i];
}
dp1[n].fi = 0;
dp1[n].se = b[n];
for(int i = n - 1;i >= 1;i --)
{
dp1[i].fi = dp1[i + 1].fi;
if(b[i] <= b[i + 1])
{
dp1[i].fi += (b[i + 1] - b[i] + 1);
b[i] += (b[i + 1] - b[i] + 1);
}
dp1[i].se = b[i];
}
answer = 1e18;
for(int i = 1;i <= n;i ++)
{
kol = 0;
if(dp[i].se == dp1[i + 1].se)
{
kol = 1;
}
answer = min(answer , max(min(dp[i].fi , dp1[i + 1].fi) + kol , max(dp[i].fi , dp1[i + 1].fi)));
}
cout << answer;
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
53 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |