| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P156SUMI - ROUND 6I - Chặt cây |
Cho n cây có chiều cao lần lượt là a[1], a[2], …, a[n]. Bạn có một chiếc cưa, mỗi lần cưa có thể giảm chiều cao của một cây đi 1 đơn vị, và phải thực hiện hoàn tất việc cưa chiếc cây này. Tuy nhiên, bạn cần nạp thêm xăng cho chiếc cưa để nó có thể hoạt động liên tục. Chiếc cưa sẽ được bổ sung năng lượng với chi phí bằng b[k], trong đó k là chỉ số lớn nhất của những chiếc cây đã bị chặt. Một cây được coi là đã bị chặt khi chiều cao của nó bằng 0. Nếu như chưa có cây nào bị chặt, bạn sẽ không thể nạp năng lượng cho chiếc cưa.
Nhiệm vụ của bạn là tính ra chi phí nhỏ nhất để có thể chặt được tất cả n cây.
Biết rằng dãy a[] là một dãy tăng dần, còn dãy b[] là một dãy giảm dần, và a[1] = 1, b[n] = 0. Bạn sẽ được cung cấp đủ lượng xăng để hạ đổ cây 1 đầu tiên.
Input
Dòng đầu tiên là số nguyên n (1 <= n <= 10^5).
Dòng thứ 2 chứa n số nguyên a[1], a[2],…, a[n] (1 <= a[i] <= 10^9).
Dòng thứ 3 chứa n số nguyên b[1], b[2],…, b[n] (1 <= b[i] <= 10^9).
Output
In ra một số nguyên là kết quả bài toán.
Example
Input:7
1 2 3 4 5 6 7
6 5 4 3 2 1 0
Output: 42
Giải thích test: Chặt cây 1 đầu tiên, sau đó chặt cây 7. Để chặt cây 7, cần nạp xăng 7 lần, mỗi lần tốn chi phí bằng b[1] = 6.
Sau khi hạ xong cây 7, tất cả các còn lại có thể hạ đổ mà không tốn năng lượng, do chi phí nạp năng lượng bằng b[7] = 0
cho mỗi lần cưa. Tổng chi phí bằng 7*6 = 42.
| Được gửi lên bởi: | adm |
| Ngày: | 2015-08-06 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
