Elearning CodePath – CTP Online Judge

Cửa hàng

SHOP

🟢 Easy #Dynamic Programming

# Cửa hàng

## Đề bài

Một cửa hàng cho thuê `N` thiết bị âm thanh. Thiết bị thứ `i` có giá thuê là $A_i$.

Để thuê hết toàn bộ `N` thiết bị, khách hàng được phép chia các thiết bị thành nhiều nhóm. Mỗi thiết bị phải thuộc đúng một nhóm. Với mỗi nhóm, tiền thuê được tính theo một trong hai quy định sau:

- Nếu nhóm có từ 3 thiết bị trở lên, khách hàng được miễn phí đúng 1 thiết bị có giá thuê nhỏ nhất trong nhóm. Các thiết bị còn lại trong nhóm phải trả đủ giá.
- Nếu nhóm có ít hơn 3 thiết bị, tất cả thiết bị trong nhóm được giảm giá `q%`.

Hãy tính tổng số tiền nhỏ nhất cần trả để thuê hết `N` thiết bị.

## Dữ liệu vào

Gồm 2 dòng:

- Dòng 1 chứa hai số nguyên dương `N, q`.
- Dòng 2 chứa `N` số nguyên dương $A_1, A_2, ..., A_N$.

## Dữ liệu ra

In ra một số nguyên duy nhất là tổng số tiền nhỏ nhất cần trả.

## Ràng buộc

- $1 ≤ N ≤ 10^6$
- $1 ≤ q < 100$
- $100 ≤ A_i ≤ 10^6$
- $A_i$ chia hết cho `100`

## Ví dụ

### Input
```text
6 10
1000 100 900 100 800 100
```

### Output
```text
2100
```

## Giải thích

Có thể chia thành 2 nhóm:

- Nhóm 1 gồm `100, 100, 100`: được miễn phí một thiết bị giá `100`, trả `100 + 100 = 200`.
- Nhóm 2 gồm `1000, 900, 800`: được miễn phí một thiết bị giá `800`, trả `1000 + 900 = 1900`.

Tổng tiền cần trả là:

```text
200 + 1900 = 2100
```

✅ Đã AC: 3 / 12 submissions