Elearning CodePath – CTP Online Judge

Bắn súng

2526_HANOI_HSG9_B5

🟢 Easy

Có N tấm bia xếp thành một hàng, đánh số 1..N. Bia i có độ bền ban đầu Ai>0; khi độ bền giảm xuống ≤0 thì coi là 0 và bia bị phá hủy.

Xạ thủ chọn một loại đạn có sức công phá nguyên dương X và dùng loại đó cho toàn bộ bài tập. Mỗi lần bắn, viên đạn trúng tấm bia đầu tiên chưa bị phá hủy, gọi là i. Bia i và các bia j phía sau (j≥i) bị giảm độ bền một lượng `max(0, X-(j-i)^2)`.

Yêu cầu: Tìm X nguyên dương nhỏ nhất để phá hủy toàn bộ bia trong không quá K lần bắn.

## Dữ liệu vào:
- Dòng 1: N,K (N≤2×10^5, K≤10^9).
- Dòng 2: N số nguyên dương Ai (Ai≤10^9).

## Kết quả: 
In X nhỏ nhất.

## Ví dụ 1
`Input`
6 3
6 7 1 3 2 1
`Output`
5
Giải thích: Với X=5, hai phát đầu bắn vào bia 1, phát thứ ba bắn vào bia 4; sau 3 phát tất cả bia bị phá hủy.

## Ví dụ 2
`Input`
3 1
3 7 3
`Output`
8
Giải thích: Chỉ được bắn một lần vào bia 1. Với X=8, sát thương lên ba bia lần lượt là 8,7,4 nên đều bị phá hủy. Với X=7, bia 2 chỉ nhận `6<7` nên chưa bị phá hủy; vì vậy X nhỏ nhất là 8.

Subtasks:
- 30%: N,K≤30 và Ai≤30.
- 20%: K=1.
- 30%: N≤1000.
- 20%: không ràng buộc thêm.

✅ Đã AC: 0 / 2 submissions