Submission #346017

#TimeUsernameProblemLanguageResultExecution timeMemory
34601712tqianPotatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
407 ms34540 KiB
#include <bits/stdc++.h> using namespace std; #define f1r(i, a, b) for (int i = a; i < b; i++) #define f0r(i, a) f1r(i, 0, a) #define eb emplace_back #define pb push_back #define f first #define s second #define sz(x) (int) (x).size() typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vl diff(n+1); f1r(i, 1, n+1) { int a, b; cin >> a >> b; diff[i] = a-b + diff[i-1]; } ll lst = 0; multiset<ll> pq; f1r(i, 1, n) { if (diff[i] < 0) { lst -= diff[i]; diff[i] = 0; } if (diff[i] > diff[n]) { lst += diff[i]-diff[n]; diff[i] = diff[n]; } lst -= diff[i]; f0r(j, 2) pq.insert(diff[i]); ll val = *pq.rbegin(); lst += val; pq.erase(prev(pq.end())); } if (sz(pq) == 0) { cout << lst << '\n'; return 0; } ll cur = *pq.rbegin(); ll slope = 0; ll bar = diff[n]; pq.erase(prev(pq.end())); while (sz(pq) && cur >= bar) { ll nxt = *pq.rbegin(); pq.erase(prev(pq.end())); if (nxt <= bar) { lst += (cur - bar) * -slope; cout << lst << '\n'; return 0; } else { lst += (cur - nxt) * -slope; slope--; } } if (cur <= bar) { cout << lst << '\n'; return 0; } lst += (cur - bar) * -slope; cout << lst << '\n'; }
#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...