1933 . 巨無霸冰淇淋

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

93.3% (42/45)

Submission's AC Ratio

45.0% (68/151)

Tags

CKsim 2016-CKsim-全國模擬

Description

為了增進觀光收益，TOI市的市長計畫在市中心建造了一支「巨無霸冰淇淋」。這支冰淇淋不但很大，完全融化所需時間也異常的長，可以在L秒內維持基本的形狀。

除了增加觀光收入外，TOI市市長也想藉由這個機會建立良好外交形象。因此，他邀請N位政界大老以及其它市的市長前往參觀。然而收到的回應實在是太熱烈，N個人所提出的參觀行程有許多重複之處，因此TOI市市長想找出一個最能提升TOI市外交形象的方案。

具體而言，TOI市市長每次接待一個人（以下簡稱為甲）的時候都需要從甲的所在地開始接待他到市中心的巨無霸冰淇淋為止。甲的出發時間xi（代表在冰淇淋建造完成後xi秒）和旅程所需時間ti（秒）是確定的，而在這段時間TOI市市長理所當然地無法接待其它人。為了簡化問題，假設市長從巨無霸冰淇淋移動到被接待人的所在地不用消耗時間，也就是說在xi+ti時刻TOI市市長可以馬上開始下一個接待行程。

雖然巨無霸冰淇淋在L秒內可以保持基本形狀，但在這L秒中他的形狀會逐漸崩壞。因此對於某個接待行程，行程結束時間愈晚，TOI市形象所提升的外交形象就愈低。具體來說，接待一個xi時刻出發並且需花ti秒移動到巨無霸冰淇淋的人為TOI市外交形象帶來的增益是C−(xi+ti)，其中C≥L。

請計算TOI市市長最多可以利用這支巨無霸冰淇淋提升多少的外交形象。

Input Format

第一行有一個正整數T，代表測資筆數。
接下來每一個測資中，第一行有三個正整數N,L,C，分別代表接待人數、冰淇淋可維持形狀的時間以及增益函數中的常數。之後的N行，每行會有兩個整數xi,ti，其中0≤xi<L，1≤ti≤L−xi，代表第i個人的出發時刻以及旅程所需時間。

Output Format

對於每筆測資，請輸出一行包含一個整數，代表TOI市市長可提升的外交形象最大值。

Sample Input 1

3
1 3 5
0 2
3 8 9
0 4
4 4
0 8
3 10 12
0 3
2 4
5 5

Sample Output 1

3
6
11

Hints

本題共有五組測試資料。每組可有多個輸入檔案，全部答對該組才得分。

第一組10分，T≤10,N≤15,L≤C≤109
第二組10分，T≤10,N≤105,L≤15,L≤C≤109
第三組20分，T≤10,N≤103,L≤C≤109
第四組20分，T≤10,N≤105,L≤103,L≤C≤109
第五組40分，T≤10,N≤105,L≤C≤109

注意事項：
使用C++作答的同學，請在程式碼開頭加上#include<cstdio>，並利用scanf讀入資料、用printf輸出資料。使用cin / cout讀入/輸出資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。

Problem Source

Problem Set / Description by Paupière
建國中學105學年度全國賽模擬賽pD

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 20
4 3 20
5 4 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
Submit out of contest
Back to Top