Submission #431808

#TimeUsernameProblemLanguageResultExecution timeMemory
431808HabitusSchools (IZhO13_school)C++14
25 / 100
337 ms73712 KiB
#include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define dec(x, y) fixed << setprecision((y)) << (x) #define xx first #define yy second #define srt(v) sort((v).begin(), (v).end()) #define srtr(v) sort((v).rbegin(), (v).rend()) #define pb push_back #define popb pop_back #define sz(a) (int)(a).size() #define len(a) (int)(a).length() #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int n, m, s; pll x[300010]; set<pll> naja, najb, raz; ll rez; int main() { ios; cin >> n >> m >> s; for(int i=0; i<n; ++i) { cin >> x[i].xx >> x[i].yy; } sort(x, x+n, greater<pll>()); for(int i=0; i<m; ++i) { rez+=x[i].xx; raz.insert({x[i].yy-x[i].xx, (ll)i}); } for(int i=m; i<n; ++i) { naja.insert({x[i].xx, (ll)i}); najb.insert({x[i].yy, (ll)i}); } int br=0; while(true) { ++br; if(s==0) break; pll pr=*prev(najb.end()); pll dr=*prev(raz.end()); pll tr=*prev(naja.end()); if(pr.xx>dr.xx+tr.xx && pr.xx>0LL) { rez+=pr.xx; --s; najb.erase(prev(najb.end())); auto it=naja.find({x[pr.yy].xx, pr.yy}); naja.erase(it); } else if(dr.xx+tr.xx>0LL) { rez+=dr.xx+tr.xx; --s; raz.erase(prev(raz.end())); naja.erase(prev(naja.end())); raz.insert({x[tr.yy].yy-x[tr.yy].xx, tr.yy}); } else break; if(br>=1000000) {cout << 1; break;} } cout << rez; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...