Codeforces Round 810 (Div. 1) |
---|
Finished |
You are given two arrays of integers $$$a_1,a_2,\dots,a_n$$$ and $$$b_1,b_2,\dots,b_m$$$.
Alice and Bob are going to play a game. Alice moves first and they take turns making a move.
They play on a grid of size $$$n \times m$$$ (a grid with $$$n$$$ rows and $$$m$$$ columns). Initially, there is a rook positioned on the first row and first column of the grid.
During her/his move, a player can do one of the following two operations:
Bob wants to maximize the score while Alice wants to minimize it. If they both play this game optimally, what is the final score of the game?
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$ (which coincide with the number of rows and columns of the grid).
The second line contains the $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^8$$$).
The third line contains the $$$m$$$ integers $$$b_1, b_2,\dots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^8$$$).
Print a single line containing the final score of the game.
2 1 3 2 2
4
4 5 235499701 451218171 355604420 132973458 365049318 264083156 491406845 62875547 175951751
531556171
In the first test case, Alice moves the rook to $$$(2, 1)$$$ and Bob moves the rook to $$$(1, 1)$$$. This process will repeat for $$$999$$$ times until finally, after Alice moves the rook, Bob cannot move it back to $$$(1, 1)$$$ because it has been visited $$$1000$$$ times before. So the final score of the game is $$$a_2+b_1=4$$$.
In the second test case, the final score of the game is $$$a_3+b_5$$$.
Name |
---|