codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2193F.md (2560B)


      1 Source: https://codeforces.com/problemset/problem/2193/F
      2 
      3 F. Pizza Delivery
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Courier YF has earned the title of the best pizza delivery person GR. The manager does not like him, so he decided to give him a very difficult task. The manager provided him with $n$ coordinates of houses $(x_i, y_i)$ where he needs to deliver the pizza. He will deliver the pizza in the following way:
     22 
     23 * GR pizza is prepared at the point ($Ax, Ay$) and YF starts the delivery from this point.
     24 * To deliver the pizza, he can move from the point ($x, y$) to three points ($x+1, y$), ($x, y+1$), ($x, y-1$).
     25 * After he has delivered all the pizzas, he returns home to the point ($Bx, By$).
     26 
     27 Each move takes him exactly one second, and handing over the pizza to the customer takes $0$ seconds. The manager wants the delivery to be as fast as possible. You need to find the minimum delivery time for all GR pizzas. It is guaranteed that delivery is always possible.
     28 
     29 Input
     30 
     31 Each test consists of several test cases. The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     32 
     33 The first line of each test case contains five integers $n$, $Ax$, $Ay$, $Bx$, $By$ ($1 \le n \le 2 \cdot 10^5$, $1 \le Ax, Ay, Bx, By \le 10^9$) — the number of houses for delivery, as well as the coordinates of the start and end points.
     34 
     35 The second line of each test case contains $n$ integers $x_1, x_2, \dots, x_n$ ($Ax \lt x_i \lt Bx$).
     36 
     37 The third line of each test case contains $n$ integers $y_1, y_2, \dots, y_n$ ($1 \le y_i \le 10^9$).
     38 
     39 It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer on a separate line — the minimum time required for pizza delivery.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 1 2 3 5 2
     53 
     54 4
     55 
     56 4
     57 
     58 3 1 3 5 2
     59 
     60 3 4 3
     61 
     62 5 4 1
     63 
     64 6 1 2 7 3
     65 
     66 5 2 3 5 5 3
     67 
     68 6 4 3 1 4 1
     69 
     70 5 6 9 8 6
     71 
     72 7 7 7 7 7
     73 
     74 3 1 8 8 3
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 6
     81 
     82 13
     83 
     84 19
     85 
     86 15
     87 ```
     88 
     89 Note
     90 
     91 Consider the second test case:
     92 
     93 * Move from the point ($Ax, Ay$) to the point ($x_3, y_3$) in $4$ seconds.
     94 * Move from the point ($x_3, y_3$) to the point ($x_1, y_1$) in $4$ seconds.
     95 * Move from the point ($x_1, y_1$) to the point ($x_2, y_2$) in $2$ seconds.
     96 * Move from the point ($x_2, y_2$) to the point ($Bx, By$) in $3$ seconds.
     97 
     98 In total, the delivery takes $4 + 4 + 2 + 3 = 13$ seconds. It can be proven that it is impossible to deliver the pizza faster.