Untitled

Lịch quảng cáo
Một cửa hàng 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.

 

Ví dụ : Có 7 khách đến quán với thời gian đến và thời gian lưu trú như sau

 

Khách truy cập 1

Khách truy cập 2

Khách truy cập 3

Khách truy cập 4

Khách thăm 5

Khách thăm 6

Khách truy cập 7

Thời gian đến

2

6

3

7

1

2

1

Khoảng thời gian

2

4

3

2

1

1

10

 

 

Chiều dài

(Các) điểm

Quảng cáo 1

1

1

Quảng cáo 2

2

2

Quảng cáo 3

3

3

 

Giả sử Ads1 hiển thị ở thời điểm thứ 2, Ads2 ở thời điểm thứ 7 và Ad3 ở thời điểm thứ 3, khách truy cập sẽ xem quảng cáo như lịch trình bên dưới:

 

Khách truy cập 1

Khách truy cập 2

Khách truy cập 3

Khách truy cập 4

Khách thăm 5

Khách thăm 6

Khách truy cập 7

Quảng cáo 1

Đồng hồ

-

-

-

-

Đồng hồ

Đồng hồ

Quảng cáo 2

-

Đồng hồ

-

Đồng hồ

-

-

Đồng hồ

Quảng cáo 3

-

-

Đồng hồ

-

-

-

Đồng hồ

(Lưu ý là khách 1 chưa xem hết Ads3 nên không được cộng điểm Ads3)

 

Số điểm mà mỗi khách truy cập có thể nhận được khi xem Quảng cáo được hiển thị như sau:

 

Khách truy cập 1

Khách truy cập 2

Khách truy cập 3

Khách truy cập 4

Khách thăm 5

Khách thăm 6

Khách truy cập 7

Quảng cáo 1

1

-

-

-

-

1

1

Quảng cáo 2

-

2

-

2

-

-

2

Quảng cáo 3

-

-

3

-

-

-

3

Tổng  12 điểm

1

2

3

2

0

1

3

(Khách 7 đã xem đầy đủ tất cả các Quảng cáo, tuy nhiên anh ta chỉ có thể nhận được mức cao nhất của một Quảng cáo - tức là 3 điểm của Quảng cáo 3)




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