ABC476 D - Automat

考え方

もし両方の販売機が両方の紙幣を受け付けるなら話は簡単。
貪欲に安い方から買っていけばいいだけである。

しかしこの問題では、ドリンクの販売機が $1$ ドル札を受け付けないこと。
$1$ ドル札だけで十分な額を持っていても、$K$ ドル札が足りなければ買えないのである。

とはいえ、ドリンク同士なら安いドリンクを買う貪欲法は成立する。
また、デザートの方も同様。

ということで、概ね以下の手順で求められる。

• 事前処理として、ひたすらドリンクだけを安い方から買った場合、最大いくつ買えるか求めておく
• その制限内でドリンクを $i$ 個買うとして、各 $i$ について以下を求める
  • ドリンクを安い方から $i$ 個買ったときの残金を求める
  • その残金でデザートを安い方からいくつ買えるか求める
  • 個数の和が最大値記録だったら更新する

安い方からいくつ買うといくら、という情報は、事前に安い順にソートして累積和を求めておけばよい。
ドリンク個数の増加に対してデザートの個数が非増加なので、ツーポインタ法で高速化できる。
メイン部分の計算量は $O(M+N)$ だが、ソートで $O(N\log N + M\log M)$ かかってしまう。

入力例1での動作

入力を受け取る。

n: 2
m: 3
k: 10
x: 50
y: 6
a: {22, 30}
b: {20, 12, 24}

デザートとドリンクをそれぞれ安い順に並べる。

a: {22, 30}
b: {12, 20, 24}

各ドリンクを買うために必要な $K$ ドル札の枚数は、順に $2,2,3$ 枚である。
累積では $2,4,7$ 枚となるので、$K$ ドル札 $6$ 枚で買えるドリンクは最大 $2$ 個である。

また、デザートとドリンクの価格の累積和は次のようになる。

sum_a: {0, 22, 52}
sum_b: {0, 12, 32, 56}

最初の所持金の合計額は $50+6\times 10=110$ ドルである。

ドリンクを $0$ 個買う場合、残金は $110$ ドルである。
デザートは $2$ 個とも買えるので、合計 $2$ 個となる。

ドリンクを $1$ 個買う場合、残金は $110-12=98$ ドルである。
デザートは $2$ 個とも買えるので、合計 $3$ 個となる。

ドリンクを $2$ 個買う場合、残金は $110-32=78$ ドルである。
デザートは $2$ 個とも買えるので、合計 $4$ 個となる。

したがって、答えは $4$ である。

注意点

$X$ は最大 $10^{15}$、$YK$ は最大 $10^{18}$ になる。
long long 型を用いること。

別解

両方混ぜた貪欲法を成立させる方法もある。
データを、デザートとドリンクを混合で「値段、kドル札要求枚数」のpairで昇順ソートしておく。
安い方から順に、「残金、残 $k$ ドル札」と比較して、買えるなら買っていく。
このとき、デザートはあとから支払うとすることで、$1$ ドル札が計算上マイナスの枚数になってもよい。

また、$1$ つ買えないドリンクがあったとしても、次のデザートは買える可能性がある。
途中で誤って処理を止めないこと。