Two Towers
Time limit2sMemory limit128 MB
Given segment lengths of a cycle of N points, find two points maximizing the shorter of the two circular path distances between them.
- Level
Medium6 of 10
- Topics
- Binary search, Prefix sum, Greedy
- Solved
- No attempts yet
Problem
There are N points numbered 1 through N, connected in order around a circle. The distance of each segment between adjacent points is given. You will build one tower at each of two different points, and you want the distance between the two towers to be as large as possible.
For any two points, there are two paths around the circle: clockwise and counterclockwise. The distance between the towers is defined as the shorter of the two path lengths.
Find the maximum possible distance between the two towers.
Input
The first line contains N (2 <= N <= 50,000).
Each of the next N lines contains the distance of one adjacent segment in order: between points 1 and 2, points 2 and 3, ..., and points N and 1. Each distance is a positive integer, and the sum of all distances is at most 1,000,000,000.
Output
Print the maximum possible distance between the two towers.