VK Cup 2012 Квалификационный раунд 1 |
---|
Закончено |
Берляндский университет готовится встретить юбилей — ему исполняется 256 лет! Специально назначенный проректор по празднованию готовится украсить университетский городок. В центре городка были воздвигнуты n ледяных скульптур. Скульптуры расположены по кругу на равном расстоянии друг от друга, то есть образуют правильный n-угольник. Они пронумерованы по порядку по часовой стрелке числами от 1 до n.
На сайте университета уже успело состояться голосование, по результатам которого каждая скульптура получила характеристику ti — степень своей привлекательности. Величины ti могут быть положительными, нулевыми или отрицательными.
Пришедший оценить работу ректор университета отметил, что, возможно, работа выполнена не идеально. Он предложил растопить некоторые скульптуры так, что:
Помогите проректору по празднованию произвести анализ замечания — найдите максимальное значение суммы ti, которое может быть получено таким способом. Разрешается не растапливать скульптуры вообще. Передвигать скульптуры нельзя.
В первой строке входных данных записано целое число n (3 ≤ n ≤ 20000) — первоначальное количество скульптур. Вторая строка содержит последовательность целых чисел t1, t2, ..., tn, ti — степень привлекательности i-ой скульптуры ( - 1000 ≤ ti ≤ 1000). Числа в строке разделяются пробелами.
Выведите искомую максимальную сумму привлекательностей скульптур.
8
1 2 -3 4 -5 5 2 3
14
6
1 -2 3 -4 5 -6
9
6
1 2 3 4 5 6
21
В первом примере наиболее оптимально оставить скульптуры через одну, то есть оставить скульптуры с привлекательностями: 2, 4, 5 и 3.
Название |
---|