P1281 [CERC1998] Copying Books

Most people's mistake: try to make earlier people copy as little as possible; if the first few people can skip, then let them skip, and output `0 0` for the corresponding person. However, the testdata has been modified to ensure that everyone has work to do.

We need to distribute $m$ ordered books to $k$ people for copying. Each person has the same copying speed. A book cannot be assigned to two (or more) people. The books assigned to each person must form a contiguous block; for example, you cannot assign the 1st, 3rd, and 4th books to the same person. Please design a plan that minimizes the total copying time. The copying time is the time taken by the person who copies the most pages.

The first line contains two integers $m,k$. The second line contains $m$ integers. The $i$-th integer indicates the number of pages in the $i$-th book.

Output $k$ lines, each with two integers. On the $i$-th line, output the starting and ending book indices assigned to the $i$-th person. The $k$ lines’ starting indices should be in increasing order. If there are multiple solutions, make the earlier people copy as little as possible.

Constraints: $1\le k \le m \le 500$, and the number of pages of each book is a positive integer not exceeding $10^4$. Translated by ChatGPT 5