Lập lịch sửa chữa ô tô

View as PDF

Submit solution


Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Mr Le Minh Hoang
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một cơ sở sửa chữa ô tô có nhận ~n~ chiếc xe để sửa chữa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết từ trước, nếu bàn giao xe thứ ~i~ quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là ~a_i~.

Ông chủ cơ sở sửa chữa quyết định sa thải toàn bộ công nhân và thuê nhân công mới. Với lực lượng mới này, ông ta dự định rằng để sửa chiếc xe thứ ~i~ sẽ cần ~b_i~ ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất.

Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô.

Input

  • Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 10000)~.
  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \leq a_i \leq 10000)~.
  • Dòng thứ ba chứa ~n~ số nguyên dương ~b_1, b_2, \ldots, b_n~ ~(1 \leq b_i \leq 100)~.

Output

  • Dòng đầu tiên ghi số tiền bị phạt tối thiểu.
  • Dòng thứ hai ghi số hiệu các xe sẽ tiến hành sửa chữa, theo thứ tự từ xe được sửa đầu tiên đến xe sửa sau cùng.

Nếu có nhiều phương án tối ưu, bạn được in ra đáp án bất kì.

Sample Input

4
1 3 4 2
3 2 3 1

Sample Output

44
4 2 3 1

Note

  • Xong công việc ~4~ vào cuối ngày ~1~, phải trả ~2 \cdot 1 = 2~.
  • Xong công việc ~2~ vào cuối ngày ~3~, phải trả ~3 \cdot 3 = 9~.
  • Xong công việc ~3~ vào cuối ngày ~6~, phải trả ~6 \cdot 4 = 24~.
  • Xong công việc ~1~ vào cuối ngày ~9~, phải trả ~1 \cdot 9 = 9~.

Số tiền tổng cộng phải trả là ~44~.

Download test và solution tạiđây.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.