{"code":"segarray","name":"Chia Dãy Số","description":"Một hôm [user:algorit] và [user:bin9638] đang đi chơi thì bị lạc vào một khu rừng tăm tối , đi được một hồi thì gặp người đàn ông , $2$ người hỏi lối ra của khu rừng thì ông ta nói rằng nếu giải được bài toán này thì cả hai người đều được chỉ lối thoát , còn không thì một trong hai người phải ở lại . Vì tính đoàn kết nên hai người này nhất quyết phải thoát ra ngoài cùng nhau . Hãy giúp hai anh chàng này thoát ra khỏi khu rừng nhé !\r\n \r\n**Bài toán như sau** : Cho một dãy số nguyên $A$ gồm $n$ phần tử và một số nguyên $k$ , hãy chia dãy số thành các dãy con không giao nhau sao cho các dãy con có tổng bằng $k$ là **nhiều nhất** .\r\n \r\n**Ví dụ** : Dãy số là **{ 2 , 1 , 1 , 1 , 1 , 2 }** và $k =$ **4** ;\r\nChúng ta sẽ chia dãy thành **{2,1,1}** và **{1,1,2}** => có hai dãy con có **tổng bằng k**.\r\n\r\n\r\n**Yêu cầu** : *Hãy đưa ra số lượng dãy có tổng bằng $k$ khi chia tối ưu.*\r\n\r\n#### Input\r\n+ Dòng thứ nhất gồm $2$ số nguyên $n$ và $k$ ($1 \\leq |k| \\leq$ $10^{15}$)\r\n+ Dòng tiếp theo là dãy số ($|A_i|$ $\\leq$ $10^9$)\r\n\r\n#### Output\r\n+ Gồm một số nguyên duy nhất là kết quả của bài toán .\r\n\r\n#### Scoring\r\n- Subtask $1$ ($20\\%$ số điểm): $n \\leq$ $10^2$ , $|A_i| \\leq 10^3$ .\r\n- Subtask $2$ ($20\\%$ số điểm): $n \\leq$ $10^3$ , $|A_i| \\leq 10^6$ .\r\n- Subtask $3$ ($60\\%$ số điểm): $n \\leq$ $10^6$ , $|A_i| \\leq 10^9$ .\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6 4\r\n        2 1 1 1 1 2\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        7 3\r\n        1 3 2 1 1 1 2\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```\r\n    \r\n    ??? warning \"Note\"\r\n\r\n        chúng ta sẽ chia dãy thành {1},{3},{2,1},{1},{1,2} , như vậy ta sẽ có được $3$ dãy con có tổng bằng $k$.","points":1600.0,"partial":true,"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}}