Submission #896535

#TimeUsernameProblemLanguageResultExecution timeMemory
896535piotrkkskaliszPotatoes and fertilizers (LMIO19_bulves)C++14
0 / 100
25 ms2776 KiB
#include <iostream> #include <queue> #include <vector> #include <stack> using namespace std; const int M = 1e5 + 10; long long pref[M]; long long f0; priority_queue <long long> P; stack <long long> stos; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, nawoz, ziemniak; cin >> n; pref[0] = 0; for (int i = 1; i <= n; i++) { cin >> nawoz >> ziemniak; pref[i] = pref[i - 1] + nawoz - ziemniak; } f0 = abs(pref[1]); if (pref[1] < 0) P.push(0); else P.push(pref[1]); long long p; //cout << "sumy prefixowe \n" << pref[1] << ' '; for (int i = 2; i < n; i++) { //cout << pref[i] << ' '; f0 += abs(pref[i]); p = P.top(); if (pref[i] < 0)// pref[i] = 0; { P.push(0); continue; } if (p <= pref[i]) { P.push(pref[i]); continue; } P.pop(); P.push(pref[i]); P.push(pref[i]); } //cout << '\n'; //cout << "rozmiar: " << P.size() << '\n'; while (!P.empty()) { p = P.top(); P.pop(); stos.push(p); } long long p1 = 0; long long p2; long long wynik = f0; //cout << "start " << f0 << '\n'; //cout << "punkty: "; for (int i = n - 1; i > 0; i--) { p2 = p1; p1 = stos.top(); //cout << p1 << ' '; if (p1 > pref[n]) { wynik -= i * (pref[n] - p2); break; } stos.pop(); wynik -= i * (p1 - p2); } //cout << "\nwynik: "; cout << wynik; return 0; } /* 7 2 0 2 0 2 0 0 5 2 0 2 0 7 0 6 6 0 1 0 0 3 1 0 0 3 1 0 5 0 5 1 0 1 0 0 5 10 0 4 0 5 7 0 0 5 3 0 1+1+4 + 4*4=24 */
#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...