Untitled

cấp 4
lịch trình 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 điểm hiển thị quảng cáo sao cho khách xem được nhiều nhất có thể.

 

Khi khách 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 là P1, P2, P3.

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

3. Khi một khách truy cập xem nhiều Quảng cáo  và đồng thời nhận được điểm cho họ, thì 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 Quảng cáo tiếp theo   có thể hiển thị ngay sau khi Quảng cáo trước đó kết thúc)

 

Cho biết độ dài của mỗi Quảng cáo L1, L2, L3 và số điểm đạt được cho 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àng nhiều điểm càng tố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 vào quán với thời gian đến và ở như sau

 

Khách 1

Khách 2

Khách 3

Khách 4

Khách 5

Khách 6

Khách 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

đ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ử rằng Quảng cáo 1 được hiển thị ở thời điểm 2, Quảng cáo 2 ở thời điểm 7 và Quảng cáo 3 ở thời điểm 3, khách truy cập sẽ xem quảng cáo theo lịch trình bên dưới:

 

Khách 1

Khách 2

Khách 3

Khách 4

Khách 5

Khách 6

Khách 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 ý rằng khách truy cập 1 đã không xem hết Ads3, vì vậy điểm của Ads3 không được trao cho anh ta)

 

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 1

Khách 2

Khách 3

Khách 4

Khách 5

Khách 6

Khách 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 cộ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 điểm 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 hiển thị và phương pháp trên cho chúng ta tổng số điểm tối đa mà khách truy cập có thể nhận được, vì vậy câu trả lời trong trường hợp này là 12.

 

[ Ràng buộc ]

- Số lượng khách N (1 ≤ N ≤ 50)

- Thời gian đến Ai, khoảng thời gian Di của mỗi 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)

- Ái + Dị ≤ 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 1 ghi T - tổng số TC (T ≤ 50)

Trong mỗi TC:

 - Dòng thứ nhất ghi N, L1, L2, L3, P1, P2, P3 theo thứ tự

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