ABC321 D問題

D問題

方針

Bをソートしておけば、ある値を境界として加算する値が$p-a_i$か$b_j$に分割できる
境界を二分探索で求め、残りの$b_j$の和は累積和を求めておけば、全体で$O(NlogM)$で計算できそう。

実装

import bisect
import itertools


def solve():
    n, m, p = read_int_list()
    a = read_int_list()
    b = read_int_list()
    b = sorted(b)

    # 累積和
    b_acm = [0] + list(itertools.accumulate(b))

    ans = 0
    for a_i in a:
        # 二分探索
        x = bisect.bisect(b, p - a_i)
        ans += a_i * x + b_acm[x] # p以下になる組み合わせの和
        ans += p * (m - x) # pより大きくなる組み合わせの和

    print(ans)


def read_int_list():
    return list(map(int, input().split()))


if __name__ == "__main__":
    solve()