Untitled
unknown
plain_text
2 years ago
13 kB
4
Indexable
/*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 Thời gian Thời lượng 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 - Xem - Xem - - Xem Quảng cáo 3 - - Xem - - - Xem (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 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. [Hạn chế] - 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) - 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 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 5 // Số test T=5 7 1 2 3 1 2 3 // Test case 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] Out đư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 #2 18 Trường hợp #3 17 Trường hợp #4 16 Trường hợp #5 17998 input 50 7 1 2 3 1 2 3 2 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 3 1 2 3 7 6 4 10 1 11 2 13 3 5 2 2 1 2 5 4 2 4 4 6 9 1 14 10 30 15 50 31 4 1 734 134 546 1 39 4 28 9 24 12 16 7 29 6 27 12 14 24 18 1 34 11 20 5 23 31 16 12 38 3 35 10 2 35 14 11 34 31 13 6 14 10 7 4 17 15 19 7 36 8 19 13 20 7 18 27 6 9 5 13 14 2 20 9 12 5 13 34 12 5 20 17 7 18 31 33 6 14 8 4 6 10 38 23 10 36 13 17 15 27 20 11 21 27 1 31 13 20 16 47 2 19 26 6 3 4 3 12 9 10 1 3 4 4 8 4 7 4 8 3 1 4 6 1 3 1 11 3 11 17 24 28 7 20 30 4 46 16 6 1 47 6 1 5 2 34 30 17 20 10 1 22 13 2 27 8 8 41 16 33 3 2 3 2 38 43 5 19 4 8 33 11 36 1 2 3 1 19 43 38 11 11 14 2 2 1 70 71 44 11 23 8 26 10 36 17 31 30 12 27 8 33 10 3 32 28 2 8 12 22 26 4 21 15 15 1 13 7 6 9 6 23 74 26 1 15 34 12 26 24 25 12 43 6 12 34 2 18 18 4 4 1 26 68 46 33 6 8 16 45 2 42 1 9 23 43 6 11 20 34 1 23 2 14 2 23 19 21 10 8 6 43 7 21 29 6 2 17 1 30 12 20 5 3 6 14 24 41 5 36 31 12 2 35 4 15 44 1 2 9 5 39 19 2 28 5 25 21 3 28 7 18 1 31 17 9 7 4 4 30 36 7 17 24 1 20 16 3 11 2 3 9 89 39 11 30 2 8 41 13 9 20 9 18 9 23 20 26 11 14 33 8 35 12 35 9 26 7 3 4 10 47 79 87 2 24 1 41 8 1 9 5 24 2 30 1 7 29 7 7 8 8 56 80 39 7 26 35 5 16 28 14 29 16 32 21 18 3 26 12 8 2 9 17 72 28 8 29 4 1 17 24 40 2 21 8 6 9 5 13 17 9 5 39 4 31 28 4 3 36 7 1 8 5 98 57 61 1 4 30 1 27 13 7 11 10 16 21 14 33 9 6 10 5 2 62 3 32 5 21 15 31 10 29 11 15 26 8 5 15 14 12 5 16 145 173 246 29 6 19 28 18 31 33 12 14 30 29 19 33 11 11 16 14 33 6 38 44 5 16 20 18 22 4 38 23 20 6 20 480 471 199 24 23 10 9 9 29 39 6 19 27 24 8 23 12 15 18 23 19 27 8 27 16 14 11 46 3 13 36 4 39 18 19 40 10 16 8 20 28 5 19 26 7 27 13 12 36 21 11 8 12 167 294 326 31 7 19 11 47 3 2 1 4 17 16 12 13 30 14 17 3 44 10 22 24 4 35 8 26 22 19 7 6 30 23 7 32 12 36 8 13 21 24 1 33 7 23 8 3 4 204 177 128 22 14 18 10 7 24 8 21 4 25 14 31 9 34 10 36 6 6 24 18 19 3 39 10 32 3 23 20 20 10 21 20 16 30 20 26 22 17 24 10 14 13 2 10 39 10 15 8 19 11 94 352 337 33 6 8 37 26 3 5 7 29 15 23 2 15 20 26 14 12 23 6 6 25 3 35 13 36 4 15 27 21 1 12 2 16 11 102 320 452 35 14 7 32 3 19 21 26 11 21 24 2 15 10 32 6 38 7 4 31 6 8 10 33 13 2 15 6 194 80 243 13 14 16 2 18 22 13 13 43 6 4 35 30 19 12 17 5 11 7 7 28 18 11 30 4 25 19 5 6 14 138 401 439 45 3 5 5 29 19 23 13 2 7 13 7 11 10 19 1 3 15 37 8 6 11 16 11 19 6 11 32 4 44 10 12 17 13 19 12 6 29 14 2 6 17 201 14 43 18 11 28 13 14 15 12 4 16 9 12 22 4 29 4 15 1 38 24 16 26 17 19 9 31 9 5 21 14 6 11 20 115 187 321 23 24 3 27 12 9 28 18 35 12 6 5 7 5 16 32 1 5 21 11 11 38 36 3 11 23 26 17 29 22 25 1 881 884 274 21 20 23 12 12 16 4 8 6 28 29 8 24 4 1 45 30 12 20 18 29 21 12 36 12 9 15 5 14 15 2 1 30 11 4 27 2 4 31 16 9 17 10 17 45 3 17 14 29 13 17 16 37 2 39 6 30 12 23 13 23 12 498 643 634 8 2 24 1 14 23 2 46 4 46 3 43 7 4 2 13 46 4 2 26 10 20 21 27 9 25 1 25 22 15 10 4 10 25 11 16 5 41 13 12 32 3 35 14 8 31 22 8 21 11 467 961 900 6 23 21 6 36 3 29 6 11 30 17 28 36 14 40 4 24 21 7 37 1 46 2 44 17 12 28 3 34 3 14 18 28 19 11 28 29 10 9 11 1 11 38 4 26 7 20 19 787 304 842 12 7 3 34 27 3 2 48 21 26 7 11 23 22 11 38 24 5 1 41 14 1 4 24 15 21 31 17 5 25 32 12 2 24 12 26 39 5 13 12 36 8 11 9 10 1 6 12 25 11 19 16 34 11 20 16 459 207 689 22 7 23 24 4 34 14 23 23 26 5 21 1 34 13 20 24 11 3 4 10 18 7 28 5 27 16 29 1 24 33 5 16 29 20 11 14 35 11 37 8 3 7 14 41 5 23 3 15 25 29 8 32 3 5 30 6 17 12 31 5 29 44 5 29 20 14 4 31 12 13 22 237 822 823 33 16 25 3 9 34 13 34 25 16 1 45 14 17 15 25 46 4 16 17 10 8 20 4 31 6 33 17 1 31 30 12 7 7 10 5 24 6 13 28 5 3 15 25 2 34 18 9 39 11 7 41 2 46 7 36 23 6 6 36 7 35 33 2 8 25 625 390 641 20 2 18 20 7 1 36 1 30 15 31 13 9 11 43 1 19 24 13 35 8 37 16 9 21 8 19 10 19 14 30 2 6 10 3 19 3 38 30 4 12 21 12 36 22 27 1 2 22 6 41 6 3 20 3 2 16 32 37 3 23 7 4 33 9 15 25 20 4 7 119 439 977 26 1 7 4 21 27 3 16 5 14 15 26 34 10 3 29 15 24 5 13 3 28 33 17 30 13 20 10 20 13 16 28 14 7 1 4 41 3 4 23 30 6 16 30 10 30 19 27 5 39 22 7 2 23 435 733 788 37 2 25 7 15 28 31 5 24 1 32 4 36 5 35 12 31 9 1 23 17 18 32 10 30 14 22 2 1 9 19 23 21 2 31 17 17 31 8 30 41 5 18 27 22 7 12 9 393 913 905 1 16 37 9 21 20 15 13 18 21 5 38 11 14 27 13 14 35 26 17 8 28 19 10 24 12 9 40 5 10 21 1 11 34 19 15 10 30 22 19 24 23 1 23 33 8 32 7 942 106 497 49 1 15 4 6 28 22 19 27 6 10 40 33 5 23 11 20 18 28 15 21 4 5 6 9 15 39 7 21 16 5 34 3 21 28 5 36 1 22 18 17 6 6 16 26 2 39 3 8 19 9 30 12 24 3 9 19 19 36 12 10 1 19 7 28 21 48 1 4 36 965 152 460 27 11 4 26 2 45 23 15 5 26 11 26 2 9 12 29 7 19 13 21 20 8 28 12 12 31 40 2 19 11 18 14 34 8 20 9 32 2 17 33 28 3 36 9 14 35 4 19 3 27 8 7 11 33 10 14 18 22 11 21 11 5 6 36 10 25 26 6 24 24 35 8 15 9 29 12 17 1 11 13 1 6 7 20 16 22 31 8 17 19 34 12 15 25 3 3 43 13 22 9 688 476 169 16 21 11 13 44 5 21 12 26 7 16 24 6 30 36 2 14 32 2 48 9 20 27 5 30 9 11 27 26 13 33 12 7 28 26 19 16 30 3 7 5 17 21 4 2 28 25 21 2 2 11 4 2 48 26 21 9 30 12 2 9 30 4 23 10 19 13 32 26 23 24 14 15 5 4 28 17 11 31 4 4 13 5 17 10 10 37 14 4 15 463 441 250 10 14 36 12 18 28 3 27 7 36 16 16 11 12 24 22 36 6 31 5 9 40 6 10 28 11 43 1 40 5 11 27 25 8 29 3 14 31 2 4 12 23 24 24 33 10 19 11 38 10 32 11 24 10 16 30 42 5 22 16 20 16 3 3 1 5 30 8 8 39 10 22 1 26 31 17 4 4 979 652 689 32 17 26 13 34 16 8 34 24 21 4 12 6 26 4 26 28 8 26 19 7 41 36 8 26 11 32 15 8 9 9 14 37 9 36 5 32 3 27 14 27 3 2 48 8 28 7 25 28 11 26 6 39 9 23 8 39 6 5 40 27 8 50 16 23 2 947 875 329 1 41 35 6 3 28 12 15 28 20 22 21 23 22 35 2 23 15 32 12 10 31 18 8 1 25 22 1 44 6 26 17 18 17 14 21 16 2 17 6 26 20 17 21 45 3 11 31 31 9 21 10 6 23 48 2 10 36 14 29 1 11 34 15 44 3 17 16 9 15 28 17 35 11 7 4 17 30 2 18 38 8 21 24 1 13 4 28 18 24 17 21 25 14 7 3 48 2 36 9 50 22 8 8 756 883 690 16 11 8 30 45 3 42 6 26 22 7 39 4 27 19 7 14 20 48 2 15 8 9 1 3 15 16 4 1 6 39 10 15 28 27 2 34 11 26 14 33 14 2 7 15 27 5 27 19 8 17 5 11 24 2 44 9 41 7 39 8 14 3 3 34 11 16 32 35 14 12 13 12 19 7 20 36 12 15 27 3 22 1 22 19 4 5 14 37 8 43 1 9 31 2 21 12 29 16 7 50 21 18 2 471 299 613 8 10 19 20 20 11 39 11 46 4 30 17 13 27 19 6 16 24 29 1 25 14 37 8 25 3 22 27 18 22 15 10 10 7 25 12 36 11 14 4 27 22 7 27 33 3 8 24 5 27 24 14 33 4 7 41 16 26 37 9 26 8 18 15 14 36 21 4 34 4 5 44 19 20 18 23 10 40 12 14 10 15 42 3 25 21 31 11 18 14 12 9 2 3 17 10 10 1 26 4 50 9 2 19 627 406 191 7 33 14 32 13 19 2 28 2 8 16 34 6 12 5 16 6 4 43 7 2 35 6 16 28 10 40 7 39 6 1 43 27 7 18 23 12 33 23 4 16 30 29 11 7 35 18 1 14 5 42 2 18 25 13 27 31 11 19 1 2 2 31 14 1 36 23 15 9 34 10 35 48 2 7 18 12 27 22 22 20 15 7 2 13 1 10 3 4 45 15 24 1 36 17 5 14 23 39 5 50 2 6 6 223 60 491 39 3 27 12 21 2 39 5 2 1 12 2 35 9 15 12 6 33 6 18 2 16 9 40 15 15 6 23 8 1 16 6 29 18 14 12 10 11 2 41 3 13 6 11 12 11 15 6 22 21 44 5 14 17 14 15 1 11 6 25 6 43 17 7 12 27 5 40 18 19 15 30 22 5 4 34 1 14 19 30 23 5 4 31 28 13 28 4 5 30 6 23 27 20 5 10 2 33 10 29 output: Case #1 12 Case #2 18 Case #3 17 Case #4 16 Case #5 17998 Case #6 65 Case #7 66 Case #8 183 Case #9 129 Case #10 43 Case #11 937 Case #12 297 Case #13 554 Case #14 507 Case #15 801 Case #16 340 Case #17 480 Case #18 560 Case #19 473 Case #20 283 Case #21 2487 Case #22 7074 Case #23 3331 Case #24 3673 Case #25 1745 Case #26 2784 Case #27 2283 Case #28 3874 Case #29 1679 Case #30 1601 Case #31 5940 Case #32 8604 Case #33 9501 Case #34 10561 Case #35 11023 Case #36 12804 Case #37 11560 Case #38 13919 Case #39 10156 Case #40 14834 Case #41 12847 Case #42 28236 Case #43 12022 Case #44 8974 Case #45 18597 Case #46 15569 Case #47 24063 Case #48 15796 Case #49 17669 Case #50 13928 */
Editor is loading...