TopCoder

Thumb tumblr nlxw0sxc2d1unbsixo1 540
Trash
><

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

19.4% (7/36)

Tags

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

0 10 3 1 2
0 9 10
3 4 8
4 3 7

Sample Output

2

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5
5 4000 65536 262144 6
6 4000 65536 262144 7
7 4000 65536 262144 8
8 4000 65536 262144 9
9 4000 65536 262144 10
10 4000 65536 262144 11
11 4000 65536 262144 12