JOI 2015 - Silk Road
Xem PDF
Điểm:
1300 (p)
Thời gian:
10.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Có \(N+1\) thành phố đánh số \(0\) đến \(N\) từ tây sang đông; khoảng cách giữa thành phố \(i-1\) và \(i\) là \(D_i\). JOI phải đi từ \(0\) đến \(N\) trong không quá \(M\) ngày. Mỗi ngày anh có thể chờ, hoặc đi một chặng về phía đông.
Thời tiết xấu của ngày \(j\) là \(C_j\). Đi chặng \(i\) vào ngày \(j\) gây mệt mỏi \(D_iC_j\); chờ không gây mệt. Hãy tìm tổng độ mệt nhỏ nhất.
Dữ liệu vào
- Dòng đầu: \(N,M\).
- \(N\) dòng tiếp: \(D_1,\ldots,D_N\), mỗi số trên một dòng.
- \(M\) dòng tiếp: \(C_1,\ldots,C_M\), mỗi số trên một dòng.
Dữ liệu ra
In tổng độ mệt nhỏ nhất.
Ràng buộc
\[
1\le N\le M\le1000,
\]
\[
1\le D_i,C_j\le1000.
\]
Ví dụ
Ví dụ 1
Input
3 5
10
25
15
50
30
15
40
30Output
1125Giải thích
Trong ví dụ 1, JOI chờ ngày 1 và 4, rồi đi vào các ngày 2, 3, 5; tổng là \(10\times30+25\times15+15\times30=1125\).
Ví dụ 2
Input
2 6
99
20
490
612
515
131
931
1000Output
31589Kỳ thi:
- JOI 2015/2015 - Vòng sơ khảo (1 Tháng 1., 2015)
Bình luận