trang chủ / đề bài / icpcwf11_f

Xưởng máy

Đề bài

Mô tả

Bạn là giám đốc của Arbitrarily Complex Machines (gọi tắt là ACM), một công ty sản xuất máy móc tiên tiến bằng những máy móc còn tiên tiến hơn. Dây chuyền sản xuất cũ đã hỏng, nên bạn cần mua máy sản xuất mới cho công ty. Mục tiêu của bạn là kiếm được nhiều tiền nhất có thể trong giai đoạn tái cơ cấu. Trong giai đoạn này bạn có thể mua và bán máy, và vận hành chúng để kiếm lời trong thời gian ACM sở hữu chúng. Do hạn chế về mặt bằng, ACM sở hữu nhiều nhất một máy tại mỗi thời điểm.

Trong giai đoạn tái cơ cấu sẽ có một số máy được rao bán. Là chuyên gia của thị trường máy móc, bạn đã biết trước giá Pi và ngày mở bán Di của từng máy Mi. Nếu bạn không mua máy Mi vào đúng ngày Di thì người khác sẽ mua nó và về sau nó không còn được bán nữa. Dĩ nhiên bạn không thể mua một máy nếu số tiền ACM đang có nhỏ hơn giá của máy đó.

Nếu mua máy Mi vào ngày Di thì ACM có thể vận hành nó bắt đầu từ ngày Di+1. Mỗi ngày máy được vận hành, nó tạo ra lợi nhuận Gi đô la cho công ty.

Bạn có thể bán một máy để thu hồi một phần giá mua vào bất kỳ ngày nào sau ngày mua nó. Mỗi máy có giá bán lại Ri trên thị trường. Bạn không thể vận hành máy vào ngày bán nó, nhưng có thể bán một máy rồi dùng tiền thu được để mua máy mới ngay trong cùng ngày.

Khi giai đoạn tái cơ cấu kết thúc, ACM sẽ bán máy mà nó còn sở hữu (nếu có). Nhiệm vụ của bạn là cực đại hóa số tiền ACM có được sau giai đoạn tái cơ cấu.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên dương N, C và D: N là số máy được rao bán, C là số đô la công ty có khi bắt đầu tái cơ cấu, D là số ngày của giai đoạn tái cơ cấu.

Mỗi dòng trong N dòng tiếp theo mô tả một máy được rao bán, gồm bốn số nguyên Di, Pi, Ri và Gi: lần lượt là ngày máy được bán, giá mua (đô la), giá bán lại (đô la) và lợi nhuận mỗi ngày khi vận hành máy.

Sau bộ test cuối cùng là một dòng gồm ba số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test và sau đó là số đô la lớn nhất ACM có thể có vào cuối ngày D+1, theo đúng định dạng Case i: x của ví dụ.

Ràng buộc

  • 1≤N≤105, 1≤C≤109, 1≤D≤109.
  • 1≤Di≤D, 1≤Ri<Pi≤109, 1≤Gi≤109.

Ví dụ

Input Output Giải thích
6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 0 0
Case 1: 44 Ngày 3 mua máy (Di,Pi,Ri,Gi)=(3,2,1,2), còn 8 đô la; vận hành ngày 4, 5 được 4 (có 12). Ngày 6 bán máy được 1 (có 13) rồi mua máy (6,12,1,3), còn 1; vận hành ngày 7 đến 20 (14 ngày) được 42 (có 43). Ngày 21 bán máy được 1: tổng 44.
3 5 10
2 4 3 1
5 6 2 3
8 20 1 10
1 10 3
2 8 1 1
0 0 0
Case 1: 17
Case 2: 10
Bộ 1: ngày 2 mua máy giá 4 (còn 1), vận hành ngày 3, 4 (có 3); ngày 5 bán được 3 (có 6) và mua máy giá 6 (còn 0); vận hành ngày 6 đến 10 được 15, ngày 11 bán được 2: tổng 17. Máy giá 20 không bao giờ mua nổi. Bộ 2: nếu mua máy vào ngày 2 thì tới ngày 4 chỉ có 2+1+1=4<10, nên tốt nhất là không mua gì.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0