# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
331340 | Nson | Potatoes and fertilizers (LMIO19_bulves) | C++14 | 363 ms | 23936 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
scanf("%d", &n);
multiset<ll> s;
ll m = 0, b = 0;
s.insert(0);
auto can_rem = [&]() {
if(s.empty()) return false;
if(m <= 0) return false;
if(*prev(s.end()) < 0) return false;
if((int)s.size() >= 2 and *prev(prev(s.end())) >= 0) return true;
return false;
};
auto smooth = [&]() {
while(can_rem()) {
m--;
b += *prev(s.end());
s.erase(prev(s.end()));
}
};
ll d = 0;
for(int i = 0; i < n; i++) {
int aa, bb;
scanf("%d %d", &aa, &bb);
aa -= bb;
d += aa;
smooth();
if(d >= 0) {
s.insert(d);
s.insert(d);
b -= d;
m += 1;
}
else {
m += 1;
b -= d;
}
// while(!s.empty() and *s.begin() < 0) s.erase(s.begin());
}
// smooth();
while(!s.empty() and *prev(s.end()) > d) {
m--;
b += *prev(s.end());
s.erase(prev(s.end()));
}
printf("%lld\n", d * m + b);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |