P2736 [USACO3.4] "Raucous Rockers"

You have just inherited the rights to $N$ ($1\le N\le20$) unreleased songs recorded by the popular "Raucous Rockers" band. You plan to select some of them to release on $M$ ($1\le M\le20$) CDs. Each CD can hold at most $T$ ($1 \le T\le20$) minutes of music, and a song cannot be split across two CDs. You may use fewer than $M$ CDs. Unfortunately, you are a classical music fan and do not know how to judge their artistic value. So you decide to choose according to the following rules: - The songs must appear on all CDs in the order they were composed, that is, the last song on disc $i$ must have been composed earlier than the first song on disc $i+1$. - The number of selected songs should be as large as possible.

The first line: three integers $N, T, M$. The second line: $N$ integers, the length of each song, in order of composition.

A single integer, the maximum number of songs that can fit on $M$ CDs.

Translation comes from NOCOW. USACO Training Section 3.4. Translated by ChatGPT 5