普段のABCよりはだいぶ難しかった。
https://atcoder.jp/contests/aising2020/tasks/aising2020_e
問題
N頭のラクダを順に並べるとする。
各ラクダiは、先頭からK[i]番目以内にいるとL[i]、それ以降だとR[i]のうれしさを得る。
任意の順で並べたとき、うれしさの最大値を求めよ。
解法
L[i]がR[i]以上であるものは前、そうでないものは後ろに寄せた方がよい。
まずラクダをその2種に分け、それぞれ考える。
前者については、L[i]-R[i]が大きいもの程優先的にK[i]以前に配置するようにするのが良い。
そこで、K[i]以前に空きがあれば、そのうちできるだけ後ろに配置しよう。
前に配置すると、他に前に配置したいものを邪魔してしまう。
K[i]以前に空きがなければできるだけ後ろに寄せる。
L[i]よりR[i]が大きい場合も同様。できるだけK[i]直後に置くようにしよう。
int T; int N; int K[202020],L[202020],R[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; ll ret=0; vector<pair<int,int>> A,B; set<int> AS,BS; FOR(i,N) { cin>>K[i]>>L[i]>>R[i]; if(L[i]>=R[i]) { ret+=R[i]; A.push_back({L[i]-R[i],K[i]}); } else { ret+=L[i]; B.push_back({R[i]-L[i],K[i]}); } } FOR(i,A.size()) AS.insert(i); FOR(i,B.size()) BS.insert(A.size()+i); sort(ALL(A)); reverse(ALL(A)); FORR(v,A) { auto it=AS.lower_bound(v.second); if(it==AS.begin()) { AS.erase(*AS.rbegin()); } else { it--; ret+=v.first; AS.erase(it); } } sort(ALL(B)); reverse(ALL(B)); FORR(v,B) { auto it=BS.lower_bound(v.second); if(it==BS.end()) { BS.erase(BS.begin()); } else { ret+=v.first; BS.erase(it); } } cout<<ret<<endl; } }
まとめ
普段のABCのFぐらいありそう。