TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

30.6% (11/36)

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 個數字是往右爬的蚯蚓,剩下的則是往左爬的蚯蚓。

對於所有測資:

  • 0s,e,ki2311
  • se
  • 1m1000
  • 1a,b
  • m(a+b)1000000

(雖然蚯蚓忽快忽慢,但從一個中繼點移動到另外一個中繼點至少需要一個時間點)

Output Format

請輸出,你沒搭在蚯蚓身上的時間,最少是多少?

(如果你提早回家了,那麼提早的時間數也算在沒搭在蚯蚓身上的時間)

Sample Input 1

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

Sample Output 1

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 (VSS, 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