## 题面

### Description

In modern data centers, people often use tape drives to store large amounts of data. There are now a total of N files numbered from 1 to N that need to be written to a single tape. The files are written in order from smallest to largest on different locations on the tape, with zero spacing between files. The size of i-the file is a_i byte

Suppose we use a tape drive with m read/write heads, any one of which can write from any position on the tape. The writing speed of the tape head is C bytes per second. These heads can not cross each other, so each read-write head can only select a continuous interval of files to write. The head is allowed to stay idle in the whole process. But one head may not halt until it has completely written all the files initiated by it to write.

We would like to know the minimum completion time for this batch of files to be completely written.

### Input

The first line contains 3 integers seperated by space. They aren,mandCas described.

The second line contains n integers where the i-th integer isa_i

1<=n,m<= 1e2, 1 <=C<= 1e2, 1 <=a_i<= 1e4

### Output

The integer which is the rounding up of the completion time (unit: second)

### Sample Input 1

5 3 45 8 3 10 7

### Sample Output 1

4

## 题解

$$f[i][j] = \min_{0 \leq k \leq i} \{\max (f[i - k][j - 1], \sum_{p=i-k+1}^i a[p])\}$$

$$\sum_{p=i-k+1}^i a[p] = s[i] - s[i - k]$$

## 代码

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 1e2+5;
int a[maxn], s[maxn], f[maxn][maxn];

int up(int n, int d) {
if (n % d) return n / d + 1;
return n / d;
}

signed main() {
int n, m, C; cin >> n >> m >> C;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(f, 0x7f, sizeof(f));
for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
for (int i = 0; i <= n; i ++) f[i] = s[i];
for (int i = 1; i <= n; i ++)
for (int j = 2; j <= m; j ++)
for (int k = 0; k <= i; k ++)
f[i][j] = min(f[i][j], max(f[i - k][j - 1], s[i] - s[i - k]));
cout << up(f[n][m], C) << endl;
return 0;
}