Thang máy vũ trụ

View as PDF

Submit solution


Points: 0.16 (partial)
Time limit: 1.58s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
USACO 3/2005
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Những con bò muốn đi vào vũ trụ! Chúng muốn đến được quỹ đạo bằng cách xây một kiểu thang máy: một cái tháp khổng lồ làm bằng các khối chồng lên nhau. Chúng có ~K~ ~(1 \leq K \leq 400)~ loại khối có thể xây tháp. Mỗi khối loại ~i~ có chiều cao ~h_i~ ~(1 \leq h_i \leq 100)~ và có số lượng ~c_i~ ~(1 \leq c_i \leq 10)~. Do khả năng bị phá hủy bởi các tia vũ trụ, không có phần nào của khối loại ~i~ có thể vượt qua độ cao ~a_i~ ~(1 \leq a_i \leq 40000)~.

Giúp những con bò xây thang máy cao nhất có thể bằng cách chồng các khối lên nhau theo luật trên.

Input

  • Dòng ~1~: Một số nguyên: ~K~
  • Dòng ~2~...~K+1~: Mỗi dòng chứa ~3~ số nguyên được phân cách bởi khoảng trắng: ~h_i, a_i~ và ~c_i~. Dòng ~i+1~ miêu tả loaị khối ~i~.

Output

Một dòng dòng duy nhất là độ cao lớn nhất của tháp có thể xây được

Sample Input

3
7 40 3
5 23 8
2 52 6

Sample Output

48

Note

Từ dưới lên: ~3~ khối loại ~2~, ~3~ khối loại ~1~, ~6~ khối loại 3. Chồng ~4~ khối loại ~2~ và ~3~ khối loại ~1~ không hợp lệ vì đỉnh của khối loại ~1~ vượt quá độ cao 40.


Comments

Please read the guidelines before commenting.



  • 0
    MrMinhFly   commented on May 21, 2021, 8:58 a.m. edited

    Hình như khai báo mảng 1e8 bị RTE hay sao ấy ạ. Mong ad check lại ạ. E dùng c++14


    • 9
      ngfam   commented on May 21, 2021, 9:38 a.m.

      Khai báo ~10^{8}~ biến int cần > ~300~MB. Bài này memlimit chỉ ~256~MB thôi bạn nhé.