| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1369085 | nikolan | Potatoes and fertilizers (LMIO19_bulves) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
/**
* Slope Trick Implementation
* Time Complexity: O(N log N)
* Space Complexity: O(N)
*/
long long solve_slope_trick() {
int n;
if (!(cin >> n)) return 0;
vector<long long> a(n), b(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
priority_queue<long long> pq;
long long current_prefix_sum = 0;
long long total_cost = 0;
for (int i = 0; i < n; i++) {
current_prefix_sum += (a[i] - b[i]);
/*
We enforce the constraint that our adjustment must be non-decreasing.
If the current prefix sum is smaller than the largest 'kink'
in our heap, it means we can reduce the total cost by
adjusting the flow.
*/
pq.push(current_prefix_sum);
if (!pq.empty() && pq.top() > current_prefix_sum) {
total_cost += pq.top() - current_prefix_sum;
pq.pop();
pq.push(current_prefix_sum);
}
}
return total_cost;
}