팥양갱이란, 주로 팥으로 만든 앙금을 틀에 부어 한천으로 굳혀서 만드는 과자이다. 지금, 정올이의 손에는 가로로 긴 직육면체 모양의 팥양갱이 하나 있다. 정올이는 오늘 간식으로 이 팥양갱을 먹을 예정이다.

이 팥양갱에는 세로 방향의 절취선이 총 N-1곳 들어 있다. 팥양갱의 길이는 L₁ + L₂ + ... + L_N이며, 각 i (1 ≦ i ≦ N-1)에 대해, i번째 절취선은 왼쪽에서 L₁ + L₂ + ... + L_i의 위치에 있다.

이 팥양갱은 통째로 먹기에는 너무 크므로, 정올이는 팥양갱에 있는 절취선 중 1곳 이상을 선택하여, 선택한 절취선을 따라 팥양갱을 잘라 여러 개의 조각으로 나누기로 하였다. 단, 조각의 크기가 고르지 않으면 보기 흉하므로, 길이가 가장 긴 조각과 가장 짧은 조각의 길이 차이가 가능한 한 작아지도록 자르기로 하였다.

길이가 가장 긴 조각과 가장 짧은 조각의 길이 차이의 최솟값을 구하라.

#8365 upload 30 done 11 how_to_reg 10 call_split Subtask

팥양갱 timer 2s memory 1024MB

#8365
Subtask

팥양갱 2s 1024MB