JOI 2023 - Freight Train - LQDOJ: Le Quy Don Online Judge

JOI 2023 - Freight Train

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 2400 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Công ty đường sắt IOI vận hành một tuyến đường sắt gồm \(N\) nhà ga nằm trên một đường thẳng, được đánh số lần lượt từ \(1\) đến \(N\). Với mỗi \(i\) (\(1 \le i \le N - 1\)), ga \(i\) và ga \(i + 1\) được nối với nhau bằng một đoạn đường ray có độ dài \(1\).

Công ty IOI nhận vận chuyển hàng hóa. Mỗi ga \(2, 3, \ldots, N\) hiện có một kiện hàng. Kiện hàng ở ga \(i\) (\(2 \le i \le N\)) có giá trị \(A_i\).

Công ty sở hữu một đoàn tàu chở hàng. Ban đầu, tàu ở ga \(1\) và có thể chạy theo cả hai chiều trên tuyến đường sắt. Tại mỗi ga, có thể xếp hàng đang ở ga đó lên tàu, hoặc dỡ hàng trên tàu xuống và để lại tại ga đó.

Công ty muốn dùng tàu để chuyển hàng từ các ga \(2, 3, \ldots, N\) về ga \(1\). Tuy nhiên, tàu chỉ chở được tối đa \(W\) kiện hàng: tại bất kỳ thời điểm nào, không được có từ \(W + 1\) kiện hàng trở lên trên tàu. Ngoài ra, do lượng nhiên liệu có hạn, tổng quãng đường tàu đi được không được vượt quá \(D\). Vì vậy, có thể không chuyển được tất cả hàng về ga \(1\).

JOI, giám đốc công ty, muốn điều khiển tàu phù hợp với các điều kiện trên để tổng giá trị hàng hóa cuối cùng được đặt tại ga \(1\) lớn nhất có thể.

Cho thông tin về tàu và hàng hóa tại các ga, hãy tìm tổng giá trị lớn nhất của hàng hóa có thể được đặt tại ga \(1\) khi kết thúc.

Dữ liệu vào

Dữ liệu vào có dạng:

N W D
A_2 A_3 ... A_N

Dữ liệu ra

In trên một dòng tổng giá trị lớn nhất của hàng hóa có thể được đặt tại ga \(1\) khi kết thúc.

Ràng buộc

\(2 \le N \le 450\).
\(1 \le W \le N - 1\).
\(2 \le D \le N^2 - N\).
\(1 \le A_i \le 1\,000\,000\) (\(2 \le i \le N\)).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

\(6\) điểm: \(W = 1\), \(A_i = 1\) với mọi \(2 \le i \le N\).
\(9\) điểm: \(A_i = 1\) với mọi \(2 \le i \le N\).
\(24\) điểm: \(W = 1\).
\(13\) điểm: \(N \le 15\).
\(24\) điểm: \(N \le 50\).
\(24\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

4 1 10
1 1 1

Output

Giải thích

Chẳng hạn, có thể điều khiển tàu như sau để tổng giá trị hàng hóa cuối cùng ở ga \(1\) bằng \(2\).

Ban đầu, tàu ở ga \(1\).
Cho tàu chạy đến ga \(2\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(2\) lên tàu. Cho tàu chạy về ga \(1\), rồi dỡ kiện hàng có giá trị \(1\) trên tàu xuống ga \(1\).
Cho tàu chạy đến ga \(4\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(4\) lên tàu. Cho tàu chạy về ga \(1\), rồi dỡ kiện hàng có giá trị \(1\) trên tàu xuống ga \(1\).

Tổng quãng đường tàu đã đi là \(8\), thỏa mãn điều kiện không vượt quá \(10\). Tổng giá trị hàng hóa cuối cùng ở ga \(1\) là \(2\). Không thể làm cho tổng giá trị này đạt từ \(3\) trở lên, nên in ra \(2\).

Ví dụ này thỏa mãn ràng buộc của tất cả các bài toán con.

Ví dụ 2

Input

7 3 16
1 1 1 1 1 1

Output

Giải thích

Chẳng hạn, có thể điều khiển tàu như sau để tổng giá trị hàng hóa cuối cùng ở ga \(1\) bằng \(5\).

Ban đầu, tàu ở ga \(1\).
Cho tàu chạy đến ga \(5\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(5\) lên tàu. Tiếp theo, cho tàu chạy đến ga \(6\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(6\) lên tàu. Cho tàu chạy về ga \(1\), rồi dỡ cả hai kiện hàng, mỗi kiện có giá trị \(1\), xuống ga \(1\).
Cho tàu chạy đến ga \(2\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(2\) lên tàu. Tiếp theo, cho tàu chạy đến ga \(3\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(3\) lên tàu. Cho tàu chạy đến ga \(4\), rồi xếp kiện hàng có giá trị \(1\) ở ga \(4\) lên tàu. Sau đó, cho tàu chạy về ga \(1\), rồi dỡ cả ba kiện hàng, mỗi kiện có giá trị \(1\), xuống ga \(1\).

Tổng quãng đường tàu đã đi là \(16\), thỏa mãn điều kiện không vượt quá \(16\). Tổng giá trị hàng hóa cuối cùng ở ga \(1\) là \(5\). Không thể làm cho tổng giá trị này đạt từ \(6\) trở lên, nên in ra \(5\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 4, 5, 6\).

Ví dụ 3

Input

5 2 12
40 30 20 10

Output

Giải thích

Chẳng hạn, có thể điều khiển tàu như sau để tổng giá trị hàng hóa cuối cùng ở ga \(1\) bằng \(100\).

Ban đầu, tàu ở ga \(1\).
Cho tàu chạy đến ga \(5\), rồi xếp kiện hàng có giá trị \(10\) ở ga \(5\) lên tàu. Cho tàu chạy đến ga \(4\), rồi xếp kiện hàng có giá trị \(20\) ở ga \(4\) lên tàu.
Cho tàu chạy đến ga \(2\). Dỡ hai kiện hàng có giá trị \(10\) và \(20\) trên tàu xuống ga \(2\). Sau đó, xếp kiện hàng có giá trị \(40\) ở ga \(2\) lên tàu.
Cho tàu chạy đến ga \(3\), rồi xếp kiện hàng có giá trị \(30\) ở ga \(3\) lên tàu. Cho tàu chạy về ga \(1\), rồi dỡ hai kiện hàng có giá trị \(30\) và \(40\) xuống ga \(1\).
Cho tàu chạy đến ga \(2\), rồi xếp hai kiện hàng có giá trị \(10\) và \(20\) đang ở ga \(2\) lên tàu. Cho tàu chạy về ga \(1\), rồi dỡ hai kiện hàng có giá trị \(10\) và \(20\) xuống ga \(1\).

Tổng quãng đường tàu đã đi là \(12\), thỏa mãn điều kiện không vượt quá \(12\). Tổng giá trị hàng hóa cuối cùng ở ga \(1\) là \(100\). Không thể làm cho tổng giá trị này đạt từ \(101\) trở lên, nên in ra \(100\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(4, 5, 6\).

Ví dụ 4

Input

5 1 11
2 7 1 8

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 4, 5, 6\).

Ví dụ 5

Input

9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(4, 5, 6\).

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

JOI 2023 - Vòng loại 2 (11 Tháng 12., 2022)