# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
817763 | tset | Growing Vegetables is Fun 4 (JOI21_ho_t1) | C++14 | 28 ms | 13188 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18+42;
signed main()
{
int N;
scanf("%lld", &N);
vector<int > v(N+1);
for(int i=1; i<=N; i++)
{
scanf("%lld", &v[i]);
}
vector<int > vMinLeft(N+2, 0);
vector<int > vMinRight(N+2, 0);
vector<int > addLeft(N+2, 0);
vector<int > addRight(N+2, 0);
vector<int > cumulLeft(N+2, 0);
vector<int > cumulRight(N+2, 0);
//vMinLeft[0] = 0;
//vMinRight[N+1] = 0;
for(int i=1; i<= N; i++)
vMinLeft[i] = max(vMinLeft[i-1] + 1, v[i]);
for(int i=N; i>=1; i--)
vMinRight[i] = max(vMinRight[i+1] + 1, v[i]);
for(int i=1; i<= N; i++)
addLeft[i] = vMinLeft[i]- v[i];
for(int i=N; i>=1; i--)
addRight[i] = vMinRight[i]- v[i];
for(int i =1; i<= N; i++)
{
cumulLeft[i] = cumulLeft[i-1];
if(addLeft[i] > addLeft[i-1])
{
cumulLeft[i] += addLeft[i] - addLeft[i-1];
}
}
for(int i=N; i>= 1; i--)
{
cumulRight[i] = cumulRight[i+1];
if(addRight[i] > addRight[i+1])
{
cumulRight[i] += addRight[i] - addRight[i+1];
}
}
int ans = min(cumulLeft[N], cumulRight[1]);
for(int i=1; i<= N; i++)
{
ans = min(ans, max(cumulLeft[i], cumulRight[i]));
}
printf("%lld\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |