제출 #530300

#제출 시각아이디문제언어결과실행 시간메모리
530300NghesPalembang Bridges (APIO15_bridge)C++14
22 / 100
249 ms12816 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<=(int)(b);++i) #define FORB(i,a,b) for(int i=(a);i>=(int)(b);--i) #define E '\n' #define name "main" #define X first #define Y second #define int ll #define ii pair<int,int> const ll oo = 1e18+19; const int N = 1e5; multiset<int> low; multiset<int> up; int numBrigde, numPeople; int pre[N+13]; int suf[N+13]; int sameside; int sumLow; int sumUp; vector<ii> people; bool minimize(ll &x, ll y){ return x > y ? x = y,1 : 0; } void ins(int x){ if (low.size() && *low.rbegin() < x) up.insert(x),sumUp += x; else low.insert(x), sumLow += x; while(up.size() > low.size()){ sumLow += *up.begin(); sumUp -= *up.begin(); low.insert(*up.begin()); up.erase(up.find(*up.begin())); } while(low.size() - 1 > up.size()){ sumLow -= *low.rbegin(); sumUp += *low.rbegin(); up.insert(*low.rbegin()); low.erase(low.find(*low.rbegin())); } } int getMed(){ return *low.rbegin(); } void prepare(){ low.clear(); up.clear(); sumUp = sumLow = 0; FOR(i,0,people.size()-1){ ins(people[i].X); ins(people[i].Y); pre[i] = sumUp - sumLow; } low.clear(); up.clear(); sumUp = sumLow = 0; FORB(i,people.size()-1,0){ ins(people[i].X); ins(people[i].Y); suf[i] = sumUp - sumLow; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout .tie(0); // freopen(name".inp","r",stdin); freopen(name".out","w",stdout); cin >> numBrigde >> numPeople; FOR(i,1,numPeople){ char Ax,By; int x,y; cin >> Ax >> x >> By >> y; if (Ax == By) sameside += abs(x - y); else people.push_back(ii(x,y)); } sort(people.begin(),people.end(),[&](ii A,ii B){ return (A.X + A.Y) < (B.X + B.Y); }); prepare(); ll res = oo; if (numBrigde == 1) res = pre[people.size()-1]; else { FOR(i,1,people.size()-1){ minimize(res,suf[i] + pre[i-1]); } } cout << res + sameside + people.size(); 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...