Codeforces Round 810 (Div. 1) |
---|
Закончено |
Вам даны два массива целых чисел $$$a_1,a_2,\dots,a_n$$$ и $$$b_1,b_2,\dots,b_m$$$.
Алиса и Боб играют в игру. Алиса ходит первой, а затем они ходят по очереди.
Они играют на доске $$$n \times m$$$ ($$$n$$$ строк и $$$m$$$ столбцов). Изначально в клетке в первой строке и первом столбце стоит ладья.
В свой ход игрок может сделать одну из следующих двух операций:
Боб хочет максимизировать счет игры, а Алиса хочет минимизировать его. Если они оба играют оптимально, каким будет итоговый счет?
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$) — длины массивов $$$a$$$ и $$$b$$$ (которые совпадают с размерами доски).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^8$$$).
Третья строка содержит $$$m$$$ целых чисел $$$b_1, b_2,\dots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^8$$$).
Выведите одну строку — итоговый счет игры.
2 1 3 2 2
4
4 5 235499701 451218171 355604420 132973458 365049318 264083156 491406845 62875547 175951751
531556171
В первом примере Алиса передвинет ладью на клетку $$$(2, 1)$$$, а Боб передвинет ладью обратно на клетку $$$(1, 1)$$$. Этот процесс повторится $$$999$$$ раз, а затем, после хода Алисы, Боб не сможет передвинуть ладью обратно на клетку $$$(1, 1)$$$, так как она уже была посещена $$$1000$$$ раз. Поэтому счет игры будет равен $$$a_2+b_1=4$$$.
Во втором примере счет игры равен $$$a_3+b_5$$$.
Название |
---|