Submission #854100

#TimeUsernameProblemLanguageResultExecution timeMemory
854100BrineTwGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms348 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define debug(x) cerr << #x << ' ' << x << '\n' #define endl '\n' #define printv(v) cerr << #v << ": "; for (auto& n: v) cerr << n << " \n"[&n==&v.back()] using namespace std; const int M = 1e9 + 7; typedef long long ll; int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N; cin >> N; vector<ll> v(N); for (auto& n: v) cin >> n; vector<ll> left(N), right(N), dpl(N), dpr(N); ll goal; dpl[0] = v[0]; dpr.back() = v.back(); for (int i = 1; i < N; i++) { goal = dpl[i] = max(dpl[i - 1] + 1, v[i]); left[i] = left[i - 1] + max(goal - v[i] - dpl[i - 1] + v[i - 1], 0LL); } for (int i = N - 2; i >= 0; i--) { goal = dpr[i] = max(dpr[i + 1] + 1, v[i]); right[i] = right[i + 1] + max(goal - v[i] - dpr[i + 1] + v[i + 1], 0LL); } //printv(left); //printv(dpl); //printv(right); //printv(dpr); ll ans = INT64_MAX; for (int i = 0; i < N; i++) { ans = min(left[i] + right[i] - min(dpl[i], dpr[i]) + v[i], ans); } cerr << "answer: "; cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...