# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1265887 | Wael | Potatoes and fertilizers (LMIO19_bulves) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#ifndef ONLINE_JUDGE
#include "deblib.h"
#else
#define debug(x...)
#endif
constexpr i64 inf = 1E18;
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
i64 ans = 0;
i64 k = 0;
priority_queue<array<i64, 2>, vector<array<i64, 2>>, greater<>> pq;
pq.push({0, inf});
for (int i = 0; i < n; ++i) {
k += b[i] - a[i];
pq.push({k, 2});
auto [v, c] = pq.top();
ans += k - v;
pq.pop();
--c;
if (c > 0) {
pq.push({v, c});
}
}
while (!pq.empty() && pq.top()[0] < k) {
ans += 1LL * (pq.top()[1] - k);
pq.pop();
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}