| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P136SUMA - SUM6 A - Xếp tháp |
Tèo có n viên gạch hình thang cân đánh số từ 1 tới n. Viên gạch thứ i có đáy nhỏ độ dài a_i, đáy lớn độ dài b_i và chiều cao h_i (a_i < b_i). Tèo muốn xếp chồng một số viên gạch lên nhau để tạo ra một hình tháp. Ngoại trừ đúng 1 viên gạch ở trên cùng, mỗi viên gạch khác trong tháp có đáy nhỏ chứa trọn vẹn đáy lớn của viên gạch duy nhất nằm trên (đáy lớn của viên gạch dưới cùng được đặt trên mặt đất).
Chiều cao của tháp là tổng chiều cao các viên gạch tạo thành.
Các bạn hãy giúp Tèo chọn các viên gạch để xây được tháp cao nhất có thể.
Input
Dòng đầu tiên là số nguyên dương n (n <= 200 000).
n dòng tiếp theo, mỗi dòng gồm 3 số a_i, b_i, h_i (<= 10^6).
Output
Dòng đầu tiên là chiều cao lớn nhất của tháp có thể xây được.
Dòng thứ hai liệt kê các viên gạch được lựa chọn, in ra theo thứ tự từ đáy tháp đi lên.
Example
Input: 6
2 3 2
4 7 4
3 5 1
1 2 2
4 5 1
5 6 1 Output: 8
2 1 4
| Được gửi lên bởi: | adm |
| Ngày: | 2013-08-25 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2022-04-03 06:50:59
QHĐ + Cây phân đoạn Last edit: 2022-04-03 06:51:31 |
|
|
2015-06-27 11:19:48 Nguyễn Vĩnh Thịnh
QHD + chặt nhị phân |
|
|
2014-11-05 16:01:55 Black Hole
QHD n^2 được 60đ :v Last edit: 2014-11-05 16:51:19 |
|
|
2014-01-13 04:09:14 kecko
Mình nghĩ QHĐ+BIT :) |
|
|
2013-11-19 06:03:46 Black Hole
chac co cach khac |
|
|
2013-11-17 04:21:01 Khủng Long Lùn
QHĐ truyền thống đc 60 điểm :) Ko biết làm sao để ăn full đây? |
|
|
2013-09-23 10:16:03 Phạm Trung Kiên C13CN3
QHĐ theo độ dài đáy :D |
|
|
2013-09-06 16:09:36 Ca Com
ai có giải thuật bài này ko nhỉ? |
