Chọn cặp (THT C1, C2 & B Vòng KVMN 2022)

Xem PDF



Tác giả:
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên \(A = (a_1, a_2, ..., a_n)\). Với hai số nguyên dương \(l, r(1 \leq l \leq r \leq n)\), gọi trọng số của cặp \((l, r)\) là tổng giá trị của các phần tử liên tiếp từ \(l\) đến \(r\) của dãy \(A\).

Yêu cầu: Cho dãy A và số nguyên k, hãy chọn ra k cặp \((l_1, r_1), (l_2, r_2), ..., (l_k, r_k)\) thõa mãn:

  • \(1 \leq l_i \leq r_i \leq n\)
  • Các cặp này đôi một khác nhau
  • \(X \leq r_i - l_i + 1\)
  • Tổng trọng số của \(k\) cặp đã chọn là lớn nhất

Input

  • Dòng đầu chứa ba số nguyên dương \(n, k, X\)
  • Dòng thứ hai chứa n số nguyên \(a_i (|a_i| \leq 10^5)\)

Output

  • Ghi ra một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100; k \leq 1000\)
  • Subtask \(2\) (\(15\%\) số điểm): \(n \leq 1000; k \leq 10^5\)
  • Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^4; k \leq 10^4\)
  • Subtask \(4\) (\(20\%\) số điểm): \(n, k \leq 5 \cdot 10^4\)
  • Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 3 \cdot 10^5\)
  • Subtask \(6\) (\(15\%\) số điểm): \(n \leq 3 \cdot 10^5; k \leq 10^7\).

Example

Test 1

Input
4 4 2
3 2 -6 8 
Output
18

Bình luận

Không có bình luận nào.