Elearning CodePath – CTP Online Judge

Trạm cứu hỏa

FIRE

Một thị trấn được mô tả bởi N ngọn đồi xếp thành một hàng. Ngọn đồi thứ i có độ cao hi. Khoảng thời gian để đi từ ngọn đồi i đến ngọn đồi i + 1 là ti phút. Một ngọn đồi i có thể nhìn thấy một ngọn đồi j nếu không có ngọn đồi k nào nằm giữa sao cho hk >= hi.

Chính quyền dự định đặt K trạm cứu hỏa tại một số ngọn đồi. Mỗi trạm cứu hỏa có thể bảo vệ tất cả các ngọn đồi mà nó có thể nhìn thấy. Thời gian để lính cứu hỏa đến một ngọn đồi nhất định là tổng thời gian di chuyển từ trạm cứu hỏa gần nhất đến ngọn đồi đó. Nếu một trạm cứu hỏa được đặt tại ngọn đồi i, thì thời gian di chuyển đến nó là si = 0.

Hãy tìm cách đặt K trạm cứu hỏa sao cho thời gian di chuyển cứu hỏa lớn nhất max(s1, s2, ..., sN) là nhỏ nhất. Nếu không thể đặt trạm theo cách hợp lệ, hãy in ra -1.

### Dữ liệu
- Dòng 1: Chứa hai số nguyên N và K (1 <= K <= N <= 500000) — số lượng ngọn đồi và số trạm cứu hỏa.
- Dòng 2: Chứa N số nguyên h1, h2, ..., hN (1 <= hi <= 10^9) — độ cao của các ngọn đồi.
- Dòng 3: Chứa N - 1 số nguyên t1, t2, ..., tN-1 (1 <= ti <= 10^9) — thời gian di chuyển giữa các ngọn đồi liên tiếp.

### Kết quả
- Nếu không thể đặt trạm hợp lệ, in ra -1. Nếu có thể, in ra số nguyên S — thời gian phản hồi lớn nhất tối thiểu.

### Ràng buộc
- Subtask 1 (10%): n, k <= 15; t1 = t2 = ... = tn = 1.
- Subtask 2 (5%): n <= 500000, k = 1.
- Subtask 3 (25%): n, k <= 200; t1 = t2 = ... = tn = 1.
- Subtask 4 (10%): n, k <= 1500.
- Subtask 5 (15%): n <= 100000, k <= 3; t1 = t2 = ... = tn = 1.
- Subtask 6 (15%): n, k <= 100000; Mỗi ngọn đồi có thể nhìn thấy 100 ngọn đồi khác.
- Subtask 7 (10%): n, k <= 100000.
- Subtask 8 (10%): Không có ràng buộc bổ sung.

### Ví dụ
Input (fire.inp):
8 3
4 4 3 4 3 2 5 4
3 5 4 7 5 9 5

Output (fire.out):
7

Input (fire.inp):
8 1
2 4 2 4 1 2 4 1
1 1 1 1 1 1 1

Output (fire.out):
-1

✅ Đã AC: 41 / 111 submissions