Chiến lược triển khai

Một công ty có nhiều máy chủ do một đội ngũ phát triển quản lý, trong đó có n máy chủ chịu trách nhiệm triển khai phần mềm. Mỗi máy chủ đều được theo dõi để ghi nhận lượng tài nguyên đã sử dụng.

Mỗi khi có phần mềm mới cần triển khai, đội ngũ phát triển cần chọn ra một dãy gồm k máy chủ từ n máy chủ ban đầu. Lượng tài nguyên mà máy chủ thứ i sử dụng được ký hiệu là $resource[i]$.

Lượng tài nguyên từ k máy chủ sẽ được tính toán và cấp phát cho phần mềm mới dựa trên lượng tài nguyên lớn nhất trong dãy $(m)$. Ví dụ: $n=3$, $k=2$, mảng tài nguyên = $[3, 1, 2]$, nếu chọn dãy độ dài k là $[3, 2]$ thì lượng tài nguyên được cấp phát cho phần mềm mới là $\max(3, 2) = 3$.

Để tránh quá tải và xung đột, đội ngũ phát triển muốn chọn dãy gồm k máy chủ sao cho không chứa hai máy chủ nào đứng cạnh nhau trong n máy chủ ban đầu.

Yêu cầu: Cho mảng tài nguyên của n máy chủ, nhiệm vụ của bạn là tìm lượng tài nguyên tối thiểu được cấp phát cho phần mềm mới từ một dãy độ dài k thỏa mãn điều kiện trên.

Đầu vào: Dòng đầu tiên chứa một số nguyên n $(1 \leq n \leq 10^5)$.

Dòng thứ i trong số n dòng tiếp theo chứa một số nguyên dương $resource[i]$ $(1 \leq resource[i] \leq 10^9)$ — lượng tài nguyên mà máy chủ thứ i sử dụng.

Dòng cuối cùng chứa một số nguyên k $(1 \leq k \leq \frac{n+1}{2})$ — độ dài của dãy máy chủ cần chọn từ n máy chủ.

Đầu ra: In ra lượng tài nguyên tối thiểu được cấp phát cho phần mềm mới.

Giải thích: Sample 1: Cho $n=4$ máy chủ với mảng tài nguyên tương ứng là $[1, 3, 5, 7]$ và đội ngũ phát triển cần chọn một dãy gồm $k=2$ máy chủ. Có 3 dãy độ dài 2 thỏa mãn điều kiện tránh quá tải và xung đột:

• $[1, 5] \Rightarrow m = 5$
• $[1, 7] \Rightarrow m = 7$
• $[3, 7] \Rightarrow m = 7$

Do đó đáp án là 5.

Sample 2: Cho $n=5$ máy chủ với mảng tài nguyên tương ứng là $[1, 3, 6, 1, 2]$ và đội ngũ phát triển cần chọn một dãy gồm $k=2$ máy chủ. Có 6 dãy độ dài 2 thỏa mãn điều kiện tránh quá tải và xung đột:

• $[1, 6] \Rightarrow m = 6$
• $[1, 1] \Rightarrow m = 1$
• $[1, 2] \Rightarrow m = 2$
• $[3, 1] \Rightarrow m = 3$
• $[3, 2] \Rightarrow m = 3$
• $[6, 2] \Rightarrow m = 6$

Do đó đáp án là 1.

Ví dụ 1:

Đầu vào:

4
1
3
5
7
2

Đầu ra:

5

Ví dụ 2:

Đầu vào:

5
1
3
6
1
2
2

Đầu ra:

1