이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define NDEBUG
#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)
#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e11;
int main() {
ll N;
cin >> N;
vector<ll> A(N);
for (ll i = 0; i < N; ++i)
{
cin >> A[i];
}
vector<ll> prefixinccost(N,-1);
vector<ll> suffixdeccost(N,-1);
prefixinccost[0]=0;
for (ll i = 1; i < N; ++i)
{
if (A[i-1]<A[i])
{
prefixinccost[i] = prefixinccost[i-1];
}
else
{
prefixinccost[i] = prefixinccost[i-1] + (A[i-1]-A[i]+1);
}
}
suffixdeccost[N-1]=0;
for (ll i = N-2; i >= 0; --i)
{
if (A[i]>A[i+1])
{
suffixdeccost[i] = suffixdeccost[i+1];
}
else
{
suffixdeccost[i] = suffixdeccost[i+1] + (A[i+1]-A[i]+1);
}
}
ll outp = INFTY;
for (ll i = 0; i < N; ++i)
{
dbg(i << ":" << suffixdeccost[i] << "," << prefixinccost[i]);
outp = min(outp, max(prefixinccost[i],suffixdeccost[i]));
}
cout << outp;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |