| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 587497 | lobo_prix | Schools (IZhO13_school) | C++17 | 0 ms | 0 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.
//[Author] tuxedcat
//[Date] 2022.07.02
//[File] src/11848.cpp
//[Library] https://github.com/tuxedcat/pslib
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/extc++.h>
using namespace std;
#define int i64
#define FP_EPS 1e-11
#define COUT_FP 11
using f64=double; //long double(살짝느림),__float128(매우느림)
//#define CPP20 1
#define DBG_SETW 3
// #define endl '\n' //remove it when interactive
#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define itos to_string
#define head(x) (x.begin())
#define tail(x) prev(x.end())
#define dbg(...) void(0)
#define dbgif(...) void(0)
#define dbg1(...) void(0)
#define dbg1if(...) void(0)
using i64=long long;using u64=unsigned long long;using u32=unsigned;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
template<class T,class CMP=less<>>using PQ=std::priority_queue<T,vector<T>,CMP>;
#if CPP20
template<class T>concept Printable=requires(T x){cout<<x<<endl;};
template<class T>concept NotPrintable=not Printable<T>;
template<class T>concept Iterable=requires(T x){x.begin();x.end();begin(x);end(x);};
#else
#define Printable class
#define NotPrintable class
#define Iterable class
#endif
//functions before include <arr.h>
//Math
#if !(CPP20)
#define countl_zero(x) __builtin_clzll(x)
#define popcount(x) __builtin_popcountll(x)
#define bit_ceil(x) 1<<clg2(x)
#endif
#if CPP20
#define sz ssize
#else
template<class T>int sz(const T& x){return x.size();}
#endif
int fdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
int cdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
i64 flg2(u64 x){return 63-countl_zero(x);}
i64 clg2(u64 x){return x-1==0?0:64-countl_zero(x-1);}
int fsqrt(i64 n) {i64 i=1;while(i*i<=n)i++;return i-1;}
int csqrt(i64 n) {i64 i=1;while(i*i<n)i++;return i;}
template<class T>T sq(T x){return x*x;}
template<class T>constexpr T inf(){return numeric_limits<T>::max()/2;}
template<class T> [[deprecated("use optional")]] constexpr T nan(){return inf<T>()+1;}
#if CPP20
template<typename T> concept MemberInf=requires(T t){t.inf();};
template<typename T> concept MemberNan=requires(T t){t.nan();};
template<MemberInf T>T inf(){return T().inf();}
template<MemberNan T> [[deprecated("use optional")]] T nan(){return T().nan();}
#endif
//IO & misc
template<class...A>void print(A...a){((cout<<a),...);}
template<class...A>void println(A...a){((cout<<a),...,(cout<<endl));}
template<class T,class U>bool assmin(T& a,U&& b){return a>b?a=b,true:false;}
template<class T,class U>bool assmax(T& a,U&& b){return a<b?a=b,true:false;}
void MUST(bool expr){
#if DEBUG
#include <csignal>
if(!expr)
raise(SIGINT);
#endif
}
#define ARG(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define lamp(expr,...) [](__VA_ARGS__){return expr;}
template<class T, class P=vector<T>>
struct Arr:public P{
Arr(){P::shrink_to_fit();}
explicit Arr(signed n):P(n){}
explicit Arr(signed n,T init):P(n,init){}
Arr(initializer_list<T>il):P(il){}
Arr(auto its, auto ite):P(its,ite){}
inline T& operator[](signed i){
int n=sz(*this);
if(i<0)i+=n,dbg1("Neg Index Found");
if(i>=n)i-=n,dbg1("Over Index Found");
return P::operator[](i);
}
const T& operator[](signed i)const{
int n=sz(*this);
if(i<0)i+=n,dbg1("Neg Index Found");
if(i>=n)i-=n,dbg1("Over Index Found");
return P::operator[](i);
}
T& at(signed i){return *this[i];}
const T& at(signed i)const{return *this[i];}
};
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}
//Consts
// const f64 pi=numbers::pi_v<f64>,eps=FP_EPS;
const f64 pi=acos(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//functions after include <arr.h>
template<class T>int argmin(const Arr<T>& a){return min_element(a.begin(),a.end())-a.begin();}
template<class T>int argmax(const Arr<T>& a){return max_element(a.begin(),a.end())-a.begin();}
Arr<int> permuinv(const Arr<int>& a){Arr<int> r(sz(a));for(int i=0;i<sz(a);i++)r[a[i]]=i;return r;}
template<class T>map<T,Arr<int>> classify(const Arr<T>& a){
map<T,Arr<int>> r;
for(int i=0;i<sz(a);i++)
r[a[i]].push_back(i);
return r;
}
#if CPP20
template<class T=int,class... Ts> requires (!Iterable<T>) tuple<T,Ts...> input(){
T x; cin>>x;
if constexpr (sizeof...(Ts)==0) return mkt(x);
else return tuple_cat(mkt(x),input<Ts...>());
}
template<class T=int,int n>std::array<T,n> input(){
std::array<T,n> a;
for(auto&i:a)
i=get<0>(input<T>());
return a;
}
string input(string& str){ cin>>str; return str; }
template<class T> requires (!Iterable<T>) T& input(T& a){ cin>>a; return a;}
template<class T> requires Iterable<T> T& input(T& a){ for(auto&i:a)input(i); return a; }
#else
#define input() [](){int x;cin>>x;return x;}()
// #define input(n) [](){Arr<int> a(n);for(auto&i:a)cin>>i;return a;}()
#endif
//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//
//지금 ordering이 unique하지 않으면 5896에서 문제가 있는데, 이유가 multiset에서 지울때,,, 왜틀리는지 모르겠다..
//usecase: BOJ5896
template<class T, class CMP, class ...Rest> struct Ordering{
static const int cmpcnt=1+sizeof...(Rest);
multiset<T,CMP> a;
Ordering<T,Rest...> b;
Ordering(CMP cmp, Rest... rest):a(cmp),b(rest...){}
int size()const{return a.size();}
void add(const T& x){a.insert(x);b.add(x);}
void del(const T& x){a.erase(a.find(x));b.del(x);}
T front(int idx, int cur=0){return cur==idx?*head(a):b.front(idx,cur+1);}
T back(int idx, int cur=0){return cur==idx?*tail(a):b.back(idx,cur+1);}
optional<T> lb(int idx, const T& x, int cur=0){
if(cur!=idx)
return b.lb(idx,x,cur+1);
auto it=a.lb(x);
return it==a.end()?optional<T>():*it;
}
optional<T> ub(int idx, const T& x, int cur=0){
if(cur!=idx)
return b.ub(idx,x,cur+1);
auto it=a.ub(x);
return it==a.end()?optional<T>():*it;
}
auto cmptor(int idx,int cur=0){
return cur==idx
?function<T(const T&,const T&)>(a.key_comp())
:b.cmptor(idx,cur+1);
}
};
template<class T, class CMP> struct Ordering<T,CMP>{
static const int cmpcnt=1;
multiset<T,CMP> a;
Ordering(CMP cmp):a(cmp){}
int size()const{return a.size();}
void add(const T& x){a.insert(x);}
void del(const T& x){a.erase(a.find(x));}
T front(int idx, int cur=0){return *head(a);}
T back(int idx, int cur=0){return *tail(a);}
optional<T> lb(int idx, const T& x, int cur=0){
auto it=a.lb(x);
return it==a.end()?optional<T>():*it;
}
optional<T> ub(int idx, const T& x, int cur=0){
auto it=a.ub(x);
return it==a.end()?optional<T>():*it;
}
auto cmptor(int idx,int cur=0){return a.key_comp();}
};
auto val2cmp(auto val){return [val](auto x, auto y){return mkp(val(x),x)<mkp(val(y),y);};}
void solve(){
auto [n,ca,cb]=input<int,3>();
auto a=ARR(n,2,0ll); input(a);
//(src:N)=1
//(N:2)=A그룹 학교가치, B그룹 학교가치
//(2:snk)=A그룹 학교개수, B그룹 학교개수
//MCMF진행: A그룹이 더 크면서 A로가는경로, B그룹이 더 크면서 B로가는경로, 작은쪽경로, 큰것2작은것residual
//작은것2큰것 residual은 (작은것+작은것2큰것)경로를 만드는데, 이건 항상 손해라서 볼필요없음.
//큰것2작은것residual은 (도시1->큰것)+(큰것->도시2->작은것)의 경로이고, 각각의 최적은
//큰것경로중최대인걸 뽑았을때 그 그룹이 다 찼다면 residual확인, 아니면 그냥추가
//
auto val_geq0=[&](int x){return mkp(a[x][0]>=a[x][1],a[x][0]);};
auto val_geq1=[&](int x){return mkp(a[x][1]>=a[x][0],a[x][1]);};
auto val_resi01=[&](int x){return -a[x][0]+a[x][1];};
auto val_resi10=[&](int x){return -a[x][1]+a[x][0];};
auto cmp_geq0=val2cmp(val_geq0);
auto cmp_geq1=val2cmp(val_geq1);
auto cmp_resi01=val2cmp(val_resi01);
auto cmp_resi10=val2cmp(val_resi10);
Ordering<int,decltype(cmp_geq0),decltype(cmp_geq1)> o(cmp_geq0,cmp_geq1);
Ordering<int,decltype(cmp_resi01)> resi01(cmp_resi01);
Ordering<int,decltype(cmp_resi10)> resi10(cmp_resi10);
for(int i=0;i<n;i++)
o.add(i);
int ans=0;
while(ca || cb){
int x=o.back(0);
int y=o.back(1);
int valx=a[x][0]>=a[x][1]?a[x][0]:-1;
int valy=a[y][1]>=a[y][0]?a[y][1]:-1;
assert(~valx or ~valy);
if(valx>=valy && ca){
ca--;
ans+=valx;
o.del(x);
resi01.add(x);
continue;
}
if(valx<=valy && cb){
cb--;
ans+=valy;
o.del(y);
resi10.add(y);
continue;
}
if(valx>=valy && cb && sz(resi01)){
//이거 최적경로 맞나? ca에 자리가 없으니 cb로 가는게 최적맞는듯?
//resi10경로도 ca자리가 없으니 안봐도 되서 최적 맞을듯.
//resi01경로와 o.b경로 두개를 비교하긴 해야할듯?
int z=resi01.back(0);
if(valy<valx+val_resi01(z)){
cb--;
ans+=valx+val_resi01(z);
o.del(x);
resi01.add(x);
resi01.del(z);
continue;
}else{
cb--;
ans+=valy;
o.del(y);
resi10.add(y);
continue;
}
}
if(valx<=valy && ca && sz(resi10)){
int z=resi10.back(0);
if(valx<valy+val_resi10(z)){
ca--;
ans+=valy+val_resi10(z);
o.del(y);
resi10.add(y);
resi10.del(z);
continue;
}else{
ca--;
ans+=valx;
o.del(x);
resi01.add(x);
continue;
}
}
}
println(ans);
}
signed main(){
// for(int ti=1,t=input();ti<=t;ti++)
// cout<<"Case #"<<ti<<": ",
solve();
}