ABC331E
解法0:
Priority queue とソートを用いて，調べる候補を減らす． \(a\)と\(b\)を降順ソートしておけば，基本的には \(a\)と\(b\)の先頭から選んでいけばよい． 今調べている\(a\)と\(b\)のインデックスの組を \(\,(i,j)\,\) とおくと， 次に調べるべきは \(\,(i+1,j)\,\) または \(\,(i,j+1)\,\) となる． これらのうち \(a\)と\(b\)の和が大きいほうが次の候補となるので， どちらを選べば良いのか判定するために priority_queue に入れてから取り出せばよい． あとは，ダメな組み合わせがあるので，それを判定すれば AC.
解法1: \(L^{1/2}\)
\(a\), \(b\) を降順ソートしておく． \(a\), \(b\) の候補をそれぞれ \(L\)個ずつ先頭から試してしまうと \(L^2\)個で TLE. そこで，\(a\), \(b\)の候補を，一方だけでも \(L^{1/2}\)程度にしてみる．
実際，\(a_{i}+b_{j}\)の組み合わせとして調べるべき組 \(\,(i,j)\,\) は，
- (\(i \in \lceil L^{1/2} \rceil\) and \(j \in M\)) or
- (\(i \in N\) and \(j \in \lceil L^{1/2} \rceil\) )
で十分．この条件を \(P\)とおく．
\(P\)の否定を考えれば， \(i \geq \lceil L^{1/2} \rceil\) and \(j \geq \lceil L^{1/2} \rceil\) となるので， \(P\) の中に上位 \(L\)個以上が含まれている．
実装の注意
ソートにより index がずれるので，駄目な組み合わせ \(L\) 個に含まれる判定に注意． 例えば，ソート前の配列を残しておけば対処できる． ソート前を残さない場合は，ソートに対応する置換を覚えておくことになる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// priority queue
int main() {
ll n,m,l;
cin >> n >> m >> l;
vector<pll> pa(n); rep(i,n) {cin >> pa[i].first; pa[i].second = i;}
vector<pll> pb(m); rep(i,m) {cin >> pb[i].first; pb[i].second = i;}
sort(all(pa), greater<pll>());
sort(all(pb), greater<pll>());
vector<ll> perma(n); rep(i,n) perma[pa[i].second] = i;
vector<ll> permb(m); rep(i,m) permb[pb[i].second] = i;
set<pll> bad;
rep(i,l){
ll c,d; cin >> c >> d;
--c, --d;
bad.insert({perma[c], permb[d]});
}
set<pll> use;
priority_queue<tuple<ll,ll,ll>> pq;
pq.push({pa[0].first + pb[0].first, 0, 0});
rep(_,l+1){
auto [val, i,j] = pq.top(); pq.pop();
if(!in(pll(i,j), bad)){
cout << val << endl;
exit(0);
}
auto f = [&](ll i, ll j) -> void {
if(i >= pa.size() || j >= pb.size()) return;
if(!in(pll(i,j), use)){
use.insert({i,j});
pq.push({pa[i].first + pb[j].first, i, j});
}
};
f(i+1, j);
f(i, j+1);
}
assert(false);
return 0;
}
// L^{1/2}
int main() {
ll n,m,l;
cin >> n >> m >> l;
// ソート前の配列も残しておく
vll a(n); rep(i,n) { cin >> a[i]; }
vll b(m); rep(i,m) { cin >> b[i]; }
// index は，ソート前の配列の物
vector<pll> pb(m); rep(i,m) pb[i] = {b[i], i};
sort(all(pa), greater<pll>());
sort(all(pb), greater<pll>());
rep(i,l){
ll c,d; cin >> c >> d;
--c, --d;
banned[c].insert(d);
}
ll ans = -1;
rep(i,n) rep(j,min(sql,m)){
if(!in(ib, banned[ia]))
}
rep(j,m) rep(i,min(sql,n)){
if(!in(ib, banned[ia]))
}
assert(ans >= 0);
cout << ans << endl;
return 0;
}
