Submission #950981

#TimeUsernameProblemLanguageResultExecution timeMemory
950981daoquanglinh2007Potatoes and fertilizers (LMIO19_bulves)C++17
0 / 100
1 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int NM = 5e5; int n, a[NM+5], b[NM+5], c[NM+5], d[NM+5], cur = 0; priority_queue <int> pq; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++){ cin >> a[i] >> b[i]; c[i] = c[i-1]+a[i]; d[i] = d[i-1]+b[i]; } pq.push(0); for (int i = 1; i < n; i++){ if (c[i]-d[i] >= pq.top()){ pq.push(c[i]-d[i]); continue; } cur += pq.top()-(c[i]-d[i]); pq.pop(); pq.push(c[i]-d[i]); pq.push(c[i]-d[i]); } int lst = pq.top(), slope = 0; while (lst > c[n]-d[n]){ cur += slope*(lst-max(c[n]-d[n], pq.top())); lst = pq.top(); pq.pop(); slope++; } cout << cur; return 0; }
#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...