Submission #844907

#TimeUsernameProblemLanguageResultExecution timeMemory
844907nskybytskyiPotatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
179 ms27332 KiB
#include <bits/stdc++.h> using namespace std; // dp[i][j] = min cost to get a[k] >= b[k] for all k <= i // and (sum (a[k] - b[k]) over k <= i) <= j // f_i(j) := dp[i][j] is decreasing and convex in j int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<pair<int, int>> ab(n); for (auto& [a, b] : ab) { cin >> a >> b; } vector<int> differences(n); for (int i = 0; i < n; ++i) { const auto& [a, b] = ab[i]; differences[i] = a - b; } vector<int64_t> prefix_sums(n + 1); for (int i = 0; i < n; ++i) { prefix_sums[i + 1] = prefix_sums[i] + differences[i]; } // looking for a non-decreasing sequence of prefix sums // with smallest possible sum of absolute differences // same problem but cannot modify prefix_sums[0]=0 and prefix_sums[n] // same as saying there are infinitely many breakpoints at 0 int64_t value{0}; priority_queue<int64_t> slope; for (int i = 1; i < n; ++i) { slope.push(prefix_sums[i]); slope.push(prefix_sums[i]); value += max<int64_t>(0, slope.top()) - prefix_sums[i]; if (slope.top() > 0) { slope.pop(); } } while (!slope.empty()) { value += max<int64_t>(0, slope.top() - prefix_sums[n]); slope.pop(); } cout << value << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...