S5. Chocolate Bar Partition
레이팅 미적용의견: 0
Maxwell has a chocolate bar that he wants to share with his friends.
The chocolate bar can be represented as a \(2\) by \(N\) array of integers \(T_{i,j}\), the tastiness of each square.
Maxwell would like to split the entire chocolate bar into connected
parts such that the average (mean) tastiness of the chocolate bar is the
same for each part. Maxwell would like to know what is the maximum
number of connected parts he can split his chocolate bar into as
described above.
A part is considered connected if you can visit every cell by moving
up, down, left or right.
The first line of input will consist of one positive integer \(N\), representing the length of the
chocolate bar.
The second line of input contains \(N\) spaced integers representing the top
row of the chocolate bar where the \(j\)-th integer from the left represents
\(T_{1,j}\).
Similarly, the third line of input contains \(N\) spaced integers representing the bottom
row of the chocolate bar where the \(j\)-th integer from the left represents
\(T_{2,j}\).
Output a single integer, representing the maximum number of connected
parts Maxwell can split his chocolate bar into.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(N=2\) — \(0 \le T_{i,j} \leq 5\) |
2 | 13점 | \(1 \le N \le 8\) — \(0 \le T_{i,j} \leq 20\) |
3 | 6점 | \(1 \le N \le 20\) — \(0 \le T_{i,j} \leq 20\) |
4 | 13점 | \(1 \le N \le 100\) — \(0 \le T_{i,j} \leq 20\) |
5 | 13점 | \(1 \le N \le 1\ 000\) — \(0 \le T_{i,j} \leq 100\) |
6 | 21점 | \(1 \le N \le 2\ 000\) — \(0 \le T_{i,j} \leq 100\ 000\) |
7 | 21점 | \(1 \le N \le 200\ 000\) — \(0 \le T_{i,j} \leq 100\ 000\ 000\) |
2
5 4
6 52An example of how to split this chocolate bar optimally into \(2\) parts is to have the bottom right
corner as its own part and the rest of the chocolate as the second part,
as shown below.
Each piece will have an average tastiness of \(5\).
5
1 0 1 2 0
0 2 0 3 15One way to get the optimal split is shown in the following
picture:
Note that each piece has an average tastiness of \(1\).
평가 및 의견
S5. Chocolate Bar Partition
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S5. Chocolate Bar Partition