| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 578439 | lobo_prix | 학교 설립 (IZhO13_school) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//[Author] tuxedcat
//[Date] 2022.06.17
//[File] src/main.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);};
#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> requires (!Iterable<T>) T input(){T x;cin>>x;return x;}
template<class T> requires Iterable<T> T input(){
T a;
for(auto&i:a)
i=input<typename remove_reference<decltype(i)>::type>();
return a;
}
template<class T=int,int n>std::array<T,n> input(){
std::array<T,n> a;
for(auto&i:a)
i=input<T>();
return a;
}
template<class T=Arr<int>> requires Iterable<T> T input(int n){
T a(n);
for(auto&i:a)
i=input<typename remove_reference<decltype(i)>::type>();
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));
//
//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>{
multiset<T,CMP> a;
Ordering(CMP cmp):a(cmp){}
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();}
};
void solve(){
int n,m,s; cin>>n>>m>>s;
auto arr=input<Arr<array<int,2>>>(n);
if(s==0){
sort(arr.begin(),arr.end(),lam(x[0]>y[0],auto x,auto y));
int res=0;
for(int i=0;i<m;i++)res+=arr[i][0];
println(res);
return;
}
if(m==0){
sort(arr.begin(),arr.end(),lam(x[1]>y[1],auto x,auto y));
int res=0;
for(int i=0;i<s;i++)res+=arr[i][1];
println(res);
return;
}
auto cmp0=lam(arr[x][0]<arr[y][0],int x,int y);
auto cmp1=lam(arr[x][1]<arr[y][1],int x,int y);
auto cmp01=lam(arr[x][0]-arr[x][1]<arr[y][0]-arr[y][1],int x,int y);
auto cmp10=lam(arr[x][1]-arr[x][0]<arr[y][1]-arr[y][0],int x,int y);
sort(arr.begin(),arr.end(),lam(x[0]>y[0],auto x,auto y));
//일단 a먼저 선택한 이후 b를 선택하자.
//각 선택마다 풋옵션을 가짐
//a에서 i를 포기(풋옵션 행사)하면 b에서 arr[i][1]의 콜옵션이 생김
//위의 초기값에서 i를 추가한다고 하자. 일단 a로 내림차순이니 a에 추가해보는건 갯수제약을 빼면 최적을 유지한다.
//제약을 무시하고 뭔가 일단 해보는건 뭔가 dual simplex의 프로세스와 비슷한 느낌이 드는데 연관성이 있을듯.
//이제 갯수문제를 해소하기 위해 a집합중에 b-a가 제일 큰걸 선택해 b로 옮겨준다. b-a가 제일큰걸 선택하는 이유: a는 어떤b집합이던 지금 상태가 최적(a오름차순으로 처리중)이므로, 다음상태로 (갯수제약을 1만큼 넘는) b집합의 최적의 a는 이전와 동일하게 유지되므로, 결과는 b-a만큼 늘어남.
//이제 b의 갯수제약을 맞추기 위해 b집합에서 제일 별로인걸 제거한다
Ordering<int,decltype(cmp10)> a(cmp10);
Ordering<int,decltype(cmp01),decltype(cmp1)> b(cmp01,cmp1);
// dbg(arr);
int cnt=0;
for(int i=0;i<m;i++) a.add(i),cnt+=arr[i][0];
for(int i=m;i<m+s;i++) b.add(i),cnt+=arr[i][1];
//a에 들어간에 b로 가는게 더 이득일동안 스왑해야할듯.
//a to b = b-a
//b to a = a-b
//위 두 metric으로 각 집합에서 뽑은게 이득일동안 교환시켜주는것 필요
auto optimize=[&](){
for(int ai=a.back(0),bi=b.back(0);
arr[ai][1]-arr[ai][0]+arr[bi][0]-arr[bi][1]>0;
ai=a.back(0),bi=b.back(0)){
a.del(ai),b.del(bi);
a.add(bi),b.add(ai);
cnt+=arr[ai][1]-arr[ai][0]+arr[bi][0]-arr[bi][1];
}
};
optimize();
int ans=cnt;
for(int i=m+s;i<n;i++){
a.add(i);
cnt+=arr[i][0];
optimize();
int j=a.back(0); a.del(j);
b.add(j);
cnt+=arr[j][1]-arr[j][0];
optimize();
int k=b.front(1); b.del(k);
cnt-=arr[k][1];
optimize();
ans=max(ans,cnt);
}
println(ans);
}
signed main(){
// for(int ti=1,t=input();ti<=t;ti++)
// cout<<"Case #"<<ti<<": ",
solve();
}