x축에는 n개의 실이 있습니다. i번째 실의 길이, 즉 T_i 는 l_i 로 표시되고 시작점의 위치는 x_i 로 표시되며 둘 다 정수입니다. 각 실에 매듭을 만들고 싶습니다. 매듭의 위치도 정수여야 합니다. 매듭은 실의 어느 지점에서나 만들 수 있으며 매듭으로 인해 실의 길이가 줄어들지 않는다고 가정합니다. 어떤 실도 다른 실에 완전히 포함되어 있지 않다고 가정할 수 있습니다. 즉, x_j ≤ x_i 이고 x_i +l_i ≤ x_j +l_j 인 두 실 T_i 와 T_j (i ≠ j) 가 없습니다.

우리는 가장 가까운 두 이웃 매듭 사이의 거리를 가능한 한 크게 하기 위해 각 실의 매듭 위치를 결정하고 싶습니다.

예를 들어, 아래 그림은 여섯 개의 실에 대한 매듭의 위치를 보여줍니다. 매듭의 위치는 점으로 표시됩니다. 모든 실은 실제로 x축에 있지만, 서로 구분하기 위해 따로 그려졌습니다. 그림 I.1에서 가장 가까운 두 매듭 사이의 거리는 20입니다. 그러나 그림 I.2와 같이 T₂ 에 대한 매듭을 다른 위치에 만들면 가장 가까운 두 매듭 사이의 거리는 25가 되며, 이것이 이 문제에서 요구하는 거리입니다.

n개의 실에 대한 정보가 주어졌을 때, 두 개의 가장 가까운 매듭 사이의 최대 거리를 계산하는 프로그램을 작성하세요.

#4392 upload 3 done 2 how_to_reg 2

Thread Knots timer 1s memory 512MB

#4392

Thread Knots 1s 512MB