Untitled

Hugo Xếp Lịch Quảng Cáo
Cửa hàng của Hugo cần hiển thị quảng cáo 3 lần một ngày.

Tuy nhiên, họ chỉ có 1 bảng điện để hiển thị quảng cáo nên nên chọn thời gian hiển thị quảng cáo để du khách có thể xem được nhiều nhất có thể.

 

Khi khách truy cập xem quảng cáo, họ có thể nhận được số điểm được tính như sau:

1. Ba quảng cáo có độ dài L1, L2, L3 và số điểm mà một người có thể nhận được sau khi xem chúng P1, P2, P3.

2. Khách truy cập chỉ có thể nhận được điểm của Quảng cáo khi xem đầy đủ Quảng cáo đó (từ đầu đến cuối Quảng cáo đó)

3. Khi khách truy cập xem nhiều Quảng cáo và nhận được điểm cho chúng, chỉ những Quảng cáo có điểm cao nhất mới được trao cho người đó.

4. Mỗi lần chỉ được hiển thị một Quảng cáo trên bảng điện (Nhưng các Quảng cáo tiếp theo có thể được hiển thị ngay sau khi Quảng cáo trước đó kết thúc)

 

Cho độ dài của mỗi Quảng cáo L1, L2, L3 và số điểm đạt được của chúng P1, P2, P3, thời gian đến của mỗi khách vào cửa hàng và thời gian họ ở lại cửa hàng, hãy viết chương trình để chọn Thời gian hiển thị quảng cáo sao cho có thể cộng được nhiều điểm nhất cho khách truy cập. In ra tổng số điểm mà khách truy cập có thể nhận được.


Có nhiều cách sắp xếp thời gian trưng bày, và cách trên cho ta tổng số điểm tối đa mà khách tham quan có thể nhận được, nên đáp án trong trường hợp này là 12.

 

[Hạn chế]

- Số lượng khách truy cập N (1  N 50)

- Thời gian đến Ai, khoảng thời gian Di của mỗi du khách và độ dài của mỗi Quảng cáo L1, L2, L3 được cho dưới dạng số nguyên (1 ≤ Ai, Di, L1, L2, L3 50)

- Ai + Di ≤ 50

- L1 + L2 + L3 50

- Thời gian bắt đầu của một Quảng cáo : 1 >< thời gian bắt đầu 50

- P1, P2, P4 là các số nguyên (1  P1, P2, P3  1000)

 

[Đầu vào]

Dòng đầu tiên ghi T - tổng số TC (T 50)

Trong mỗi TC:

  - Dòng 1 ghi N, L1, L2, L3, P1, P2, P3 theo thứ tự này

  - N dòng tiếp theo: mỗi dòng ghi thời gian đến Ai và thời gian Di của mỗi du khách

5 // Số ca kiểm thử T=5

7 1 2 3 1 2 3 // Trường hợp thử nghiệm 1 N=7, L1=1, L2=2, L3=3, P1=1, P2=2, P3=3

2 2 // A1 = 2, D1 = 2

6 4 // ...

3 3

7 2

1 1

2 1

1 10

4 3 2 1 6 4 3

1 5

1 3

2 4

2 2

...

 

[Đầu ra]

Đưa ra tổng số điểm tối đa mà khách truy cập có thể nhận được khi xem quảng cáo.

Trường hợp 1

12

Trường hợp số 2

18

Trường hợp số 3

17

Trường hợp số 4

16

Trường hợp số 5

17998