TopCoder

Thumb tumblr nlxw0sxc2d1unbsixo1 540
Trash
><

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

27.3% (3/11)

Tags

Description

你是一隻專門寄生在蚯蚓身上的寄生蟲。

你現在正在一條長條形道路的最左端(也就是你家)。

你知道這條道路上有很多條蚯蚓,有些蚯蚓只會由左往右爬有些則是只會從右往左爬。

蚯蚓是種很神祕的生物,所以他們爬行的速度並非等速,可能忽快忽慢。

而且所有的蚯蚓一但爬到道路的端點之後就不會再動了。

而你很威,你已經知道在什麼時間哪一隻蚯蚓會爬過哪個中繼點。

現在你很想傳染病菌給這些蚯蚓,但是你還有事,必須在時間點 e 以前回家。

而且寄生蟲自己移動太慢了,所以你只能搭在蚯蚓身上移動,

你也可以在中繼點跳下蚯蚓,等另一隻蚯蚓繼續搭上他旅行。

你希望在有限的時間內,能夠有盡量多的時間待在蚯蚓身上(以感染他們)。

給你這些移動的蚯蚓的資訊以及現在時間與回家時間,你想要一種策略使沒搭在蚯蚓身上的時間最少並請輸出那個數字。

另外, 由於有的蚯蚓有點胖, 會占住道路, 所以同時只會有一隻蚯蚓經過同一個中繼點。

(你可以假設在蚯蚓經過中繼點的瞬間你就可以跳上他, 而且道路的最兩端也算中繼點)

Input Format

第一行有五個整數 s, e, m, a, b

代表現在是時間 s 而你必須在時間 e 前回家.

而路上共有 m 個中繼點, a 條往右爬的蚯蚓, b 條往左爬的蚯蚓

接下來有 m 行, 每行有 a + b 個整數 描述一個中繼點

其中的第 i 個數字 ki 代表第 i 隻蚯蚓在 ki 時間點會經過此中繼點

這 a + b 個數字的前 a 個數字是往右爬的蚯蚓, 剩下則是往左爬的蚯蚓.

0 <= s, e, ki <= 231 - 1
s <= e
1 <= m <= 1000
1 <= a, b
m * (a + b) <= 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

Subtasks

For Testdata: 0 ~ 0, Score: 8
For Testdata: 1 ~ 1, Score: 8
For Testdata: 2 ~ 2, Score: 8
For Testdata: 3 ~ 3, Score: 8
For Testdata: 4 ~ 4, Score: 8
For Testdata: 5 ~ 5, Score: 8
For Testdata: 6 ~ 6, Score: 8
For Testdata: 7 ~ 7, Score: 8
For Testdata: 8 ~ 8, Score: 8
For Testdata: 9 ~ 9, Score: 8
For Testdata: 10 ~ 10, Score: 8
For Testdata: 11 ~ 11, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 65536 262144
1 4000 65536 262144
2 4000 65536 262144
3 4000 65536 262144
4 4000 65536 262144
5 4000 65536 262144
6 4000 65536 262144
7 4000 65536 262144
8 4000 65536 262144
9 4000 65536 262144
10 4000 65536 262144
11 4000 65536 262144