Increasing Array
Count the minimum total increment needed to make the array non-decreasing.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
You may increase array elements, but never decrease them. Find the minimum total amount added so that the final array becomes non-decreasing.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Process the array from left to right and keep the largest value that the current position is allowed to have without breaking the non-decreasing order.
If the next element is already at least that large, it can stay as it is and it becomes the new running maximum.
If the next element is smaller, then the cheapest possible fix is to raise it exactly up to the running maximum. Any larger increase would only add unnecessary cost.
So every step is forced:
keep the value if it is large enough
otherwise add the difference to the answer and pretend the value became the previous maximum
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n)\)
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
int n;
std::cin >> n;
std::int64_t answer = 0;
std::int64_t current_max = 0;
for (int i = 0; i < n; ++i) {
std::int64_t value;
std::cin >> value;
if (i == 0) {
current_max = value;
continue;
}
if (value < current_max) {
answer += current_max - value;
} else {
current_max = value;
}
}
std::cout << answer << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
The accumulated answer can become large, so store it in a 64-bit integer.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.