TopCoder

Thumb head icon
bb
師宇好可愛

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

18.2% (26/143)

Description

某保全公司有N 位保全人員(以1,2,…,N 表示)。這家公司白天要負責N 個地區的守衛工作,晚上也要負責另外N 個地區的守衛工作。保全公司對每個地區都有評估其危險程度值,此數值是一個正整數。白天要守衛的N 個地區,其危險程度值分別記為x1, x2, …, xN;晚上要守衛的N 個地區,其危險程度值分別記為y1, y2, …, yN。每位保全人員需負責白天時段某個地區和晚上時段某個地區的守衛工作,每一個地區都必需要有保全人員(且剛好一位)來負責守衛。保全公司同意一個保全人員如果從事危險的工作,則會支付他(她)合理的危險加給,但又不願意保全人員為賺取危險加給而選擇太危險工作。所以,這家保全公司制定了以下的規定:
規定一、假設保全人員白天工作地區的危險程度為x,而晚上工作地區的危險程度為y,則其全天的工作危險程度為x+y。如果x+y 小於L,則保全公司不支付任何危險加給;如果x+y 介於L 和U 之間(亦即L ≤ x+y ≤ U),則保全公司支付危險加給x+y-L。如果x+y 大於U,則保全公司將支付危險加給U-L。
另一方面,為了避免保全人員來回奔波,保全公司也制定了另一條規定:
規定二、如果白天工作地區i (其危險程度為xi) 和晚上工作地區j (其危險程度為yj) 距離太遠,則不允許保全人員一天同時在i 和j 兩地區工作。我們稱i 和j 為禁止配對。
給定N 個白天工作地區的危險程度值、N 個晚上工作地區的危險程度值、L、U 及集合F 包含K 個禁止配對(0 ≤ K ≤ N2),請寫一個程式幫保全公司計算所要支付的最少危險加給費用為何?若條件造成無法讓每位保全人員都能順利分配到白天和晚上各一個守衛地區,則請輸出no。

Input Format

第一行有一個數字T 代表測試資料的數目,T ≤ 8。每組測資的第一行有4 個數字,代表N 值、L 值、U 值與K 值,任兩個數字以空白隔開。第二行起接下來K 行代表K個禁止配對,每個禁止配對有二個數字(兩個數字間以空白隔開):第一個數字代表白天的地區; 第二個數字代表晚上的地區。每組測資的最後兩行分別代表白天要守衛的N 個地區的危險程度值及晚上要守衛的N 個地區的危險程度值,兩行中的第一行有N 個數字(任兩個數字以空白隔開)代表x1, x2, …, xN,兩行中的第二行也有N 個數字(任兩個數字以空白隔開)代表y1, y2, …, yN

Output Format

針對所輸入的資料,輸出一個正整數代表保全公司所要支付的最少危險加給。若條件造成無法讓每位保全人員都能順利分配到白天和晚上各一個守衛地區,則輸出no。

Sample Input

輸入範例1:
2
5 2 100 0
4 1 3 2 5
9 7 8 10 6
5 2 100 5
1 1
1 2
1 3
1 4
1 5
4 1 3 2 5
9 7 8 10 6

輸入範例2:
3
5 6 100 0
1 7 8 9 10
1 2 3 4 5
5 6 100 1
1 5
1 7 8 9 10
1 2 3 4 5
5 6 100 2
1 4
1 5
1 7 8 9 10
1 2 3 4 5

輸入範例3:
2
5 2 9000000000000000002 0
4000000000000000003 4000000000000000003 4000000000000000002 4000000000000000002 4000000000000000002
5000000000000000003 5000000000000000003 5000000000000000002 5000000000000000002 5000000000000000002
5 2000000000000000 100000000000000000 5
1 1
1 2
1 3
1 4
1 5
4000000000000000 1000000000000000 3000000000000000 2000000000000000 5000000000000000
9000000000000000 7000000000000000 8000000000000000 10000000000000000 6000000000000000

Sample Output

輸出範例1:
45
no

輸出範例2:
20
21
22

輸出範例3:
45000000000000000000
no

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組11 分:
(1) 1 ≤ N ≤ 10
(2) 1 ≤ x1, x2, …, xN, y1, y2, …, yN ≤ 10
(3) 1 ≤ L, U ≤ 20
(4) 0 ≤ K ≤ 100
第二組13 分:
(1) 1 ≤ N ≤ 100
(2) 1 ≤ x1, x2, …, xN, y1, y2, …, yN ≤ 100
(3) 1 ≤ L ≤ 1000
(4) max1≤ i ≤ N xi+max1≤ j ≤ N yj ≤ U
(5) K=0
第三組21 分:
(1) 1≤N≤1000
(2) x1 = x2 = … = xN = y1 = y2 = … = yN = 1
(3) 1 ≤ L ≤ 1000
(4) max1≤ i ≤ N xi+max1≤ j ≤ N yj ≤ U
(5) 0 ≤ K ≤ 1000000
第四組25 分:
(1) 1 ≤ N ≤ 500
(2) 1 ≤x1, x2, …, xN, y1, y2, …, yN ≤ 10000
(3) 1 ≤ L, U ≤ 10000
(4) 0 ≤ K ≤ 250000
第五組30 分:
(1) 1 ≤ N ≤ 500
(2) 1 ≤ x1, x2, …, xN, y1, y2, …, yN ≤ 1018
(3) 1 ≤ L, U ≤ 9×1018
(4) 0 ≤ K ≤ 250000

Problem Source

104學年度高級中學資訊學科能力競賽決賽程式設計試題第七題
Set by Paupière

Subtasks

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 13
For Testdata: 2 ~ 2, Score: 21
For Testdata: 3 ~ 3, Score: 25
For Testdata: 4 ~ 4, Score: 30
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 8000 131072 65536
1 8000 131072 65536
2 8000 131072 131072
3 8000 131072 65536
4 8000 131072 65536