Submission #1208964

#TimeUsernameProblemLanguageResultExecution timeMemory
1208964dima2101Growing Vegetables is Fun 4 (JOI21_ho_t1)C++20
100 / 100
18 ms6648 KiB
#include <bits/stdc++.h> #define int long long signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n; std::cin >> n; std::vector<int> a(n); std::vector<int> d(n - 1); for (int i = 0; i < n; i++) { std::cin >> a[i]; } for (int i = 0; i < n - 1; i++) { d[i] = (a[i + 1] - a[i]); } std::vector<int> pref(n - 1); for (int i = 0; i < n - 1; i++) { if (i == 0) { if (d[i] <= 0) { pref[i] = std::abs(d[i]) + 1; } } else { if (d[i] <= 0) { pref[i] = pref[i - 1] + std::abs(d[i]) + 1; } else { pref[i] = pref[i - 1]; } } } std::vector<int> suf(n - 1); for (int i = n - 2; i >= 0; i--) { if (i == n - 2) { if (d[i] >= 0) { suf[i] = d[i] + 1; } } else { if (d[i] >= 0) { suf[i] = suf[i + 1] + d[i] + 1; } else { suf[i] = suf[i + 1]; } } } int best = 1e15; best = std::min(pref.back(), suf[0]); for (int i = 1; i < n - 1; i++) { best = std::min(best, std::max(pref[i - 1], suf[i])); } std::cout << best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...