Submission #48143151

---

Source Code Expand

import sys
import heapq
from typing import List, Tuple

sys.setrecursionlimit(210000)


def eprint(*args, **kwargs):
    print(
        '[EPRINT]',
        *args, file=sys.stderr, **kwargs)


def main() -> None:
    _, _, L = map(int, input().split())
    mains = list((p, i) for i, p in enumerate(map(int, input().split())))
    subs = list((p, i) for i, p in enumerate(map(int, input().split())))
    bans = set(tuple(map(int, input().split())) for _ in range(L))

    mains.sort(reverse=True)
    subs.sort(reverse=True)
    queue: List[Tuple[int, int, int, int, int]] = []
    heapq.heappush(queue, (-mains[0][0] - subs[0][0], 0, 0, mains[0][1], subs[0][1]))

    while True:
        price, i, j, midx, sidx = heapq.heappop(queue)
        if (midx + 1, sidx + 1) not in bans:
            print(-price)
            break

        heapq.heappush(
            queue, (-mains[i + 1][0] - subs[j][0], i + 1, j, mains[i + 1][1], subs[j][1]))
        heapq.heappush(
            queue, (-mains[i][0] - subs[j + 1][0], i, j + 1, mains[i][1], subs[j + 1][1]))


if __name__ == '__main__':
    main()

Submission Info

Judge Result