{"code":"22_tht_khuvucmiennam_bc_4","name":"Chọn cặp (THT C1, C2 & B  Vòng KVMN 2022)","description":"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$.\r\n\r\n**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:\r\n\r\n- $1 \\leq l_i \\leq r_i \\leq n$\r\n- Các cặp này đôi một khác nhau\r\n- $X \\leq r_i - l_i + 1$\r\n- Tổng trọng số của $k$ cặp đã chọn là lớn nhất\r\n\r\n#### Input \r\n- Dòng đầu chứa ba số nguyên dương $n, k, X$\r\n- Dòng thứ hai chứa n số nguyên $a_i (|a_i| \\leq 10^5)$\r\n\r\n#### Output\r\n- Ghi ra một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.\r\n\r\n#### Scoring\r\n- Subtask $1$ ($10\\%$ số điểm): $n \\leq 100; k \\leq 1000$\r\n- Subtask $2$ ($15\\%$ số điểm): $n \\leq 1000; k \\leq 10^5$\r\n- Subtask $3$ ($20\\%$ số điểm): $n \\leq 10^4; k \\leq 10^4$\r\n- Subtask $4$ ($20\\%$ số điểm): $n, k \\leq 5 \\cdot 10^4$\r\n- Subtask $5$ ($20\\%$ số điểm): $n, k \\leq 3 \\cdot 10^5$\r\n- Subtask $6$ ($15\\%$ số điểm): $n \\leq 3 \\cdot 10^5; k \\leq 10^7$.\r\n\r\n#### Example \r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 4 2\r\n        3 2 -6 8 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        18\r\n        ```","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}