1604 . 蚯蚓之寄生蟲問題
Description
你是一隻專門寄生在蚯蚓身上的寄生蟲。
你現在正在一條長條形道路的最左端（也就是你家）。
你知道這條道路上有很多條蚯蚓，有些蚯蚓只會由左往右爬有些則是只會從右往左爬。
蚯蚓是種很神祕的生物，所以他們爬行的速度並非等速，可能忽快忽慢。
而且所有的蚯蚓一但爬到道路的端點之後就不會再動了。
而你很威，你已經知道在什麼時間哪一隻蚯蚓會爬過哪個中繼點。
現在你很想傳染病菌給這些蚯蚓，但是你還有事，必須在時間點 $e$ 以前回家。
而且寄生蟲自己移動太慢了，所以你只能搭在蚯蚓身上移動，
你也可以在中繼點跳下蚯蚓，等另一隻蚯蚓繼續搭上他旅行。
你希望在有限的時間內，能夠有盡量多的時間待在蚯蚓身上（以感染他們）。
給你這些移動的蚯蚓的資訊以及現在時間與回家時間，你想要一種策略使沒搭在蚯蚓身上的時間最少並請輸出那個數字。
另外，由於有的蚯蚓有點胖，會占住道路，所以同時只會有一隻蚯蚓經過同一個中繼點。
你可以假設在蚯蚓經過中繼點的瞬間你就可以跳上他，而且道路的最兩端也算中繼點。
Input Format
第一行有五個整數 $s, e, m, a, b$，
代表現在是時間 $s$ ，你必須在時間 $e$ 前回家，
而路上共有 $m$ 個中繼點， $a$ 條往右爬的蚯蚓， $b$ 條往左爬的蚯蚓。
接下來有 $m$ 行，每行有 $a + b$ 個整數，描述一個中繼點，
其中的第 $i$ 個數字 $k_i$ 代表第 $i$ 隻蚯蚓在 $k_i$ 時間點會經過此中繼點。
這 $a + b$ 個數字的前 $a$ 個數字是往右爬的蚯蚓，剩下的則是往左爬的蚯蚓。
對於所有測資：
- $0 \leq s, e, k_i \leq 2 ^ {31} - 1$
- $s \leq e$
- $1 \leq m \leq 1000$
- $1 \leq a, b$
- $m * (a + b) \leq 1000000$
（雖然蚯蚓忽快忽慢，但從一個中繼點移動到另外一個中繼點至少需要一個時間點）
Output Format
請輸出，你沒搭在蚯蚓身上的時間，最少是多少？
（如果你提早回家了，那麼提早的時間數也算在沒搭在蚯蚓身上的時間）
Sample Input 1
0 9 10
3 4 8
4 3 7
Sample Output 1
Hints
時間點 0 時你搭上了第 1 隻蚯蚓, 且在時間點 3 時跳下來,
在時間點 4 時跳上第 2 隻蚯蚓, 在時間點 9 時回到家
所以沒搭在蚯蚓身上的時間是 (4 - 3) + (10 - 9) = 2
Problem Source
原TIOJ1604 / Problem Setter: coquelicot
2021.02.09 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 8 |
| 2 | 1 | 8 |
| 3 | 2 | 8 |
| 4 | 3 | 8 |
| 5 | 4 | 8 |
| 6 | 5 | 8 |
| 7 | 6 | 8 |
| 8 | 7 | 8 |
| 9 | 8 | 8 |
| 10 | 9 | 8 |
| 11 | 10 | 8 |
| 12 | 11 | 12 |