2sec
Най-хубавият
имот на
селянина Йон
представлява
редица от
ябълкови
дървета,
номерирани с
числата от 1
до N.
От известно
време Йон
почувствал,
че силите му
намаляват и
решил да даде
част от дърветата
на своите
двама сина.
По-малкият от
синовете
създавал
доста
неприятности
на баща си и
затова Йон
решил
следното:
-
всеки от
синовете ще
получи
дървета,
разположени
на
последователни
позиции в
редицата от
ябълки;
- броят на
ябълките за
всеки от
синовете може
да бъде
различен, но
всеки син ще
получи поне
по едно
дърво;
- малкият син
ще получи
дървета с
по-малки номера
от номерата
на дърветата,
предназначени
за големия
син;
- разликата
между
приходите на
големия син от
получените
дървета и
приходите на
малкия син
трябва да
бъде
максимална.
Приходите,
които носи
едно отделно
дърво са
пресметнати
от Йон по
специална
формула,
която той е
усъвършенствал
през
годините.
Задача
Напишете
програма,
която намира
търсената
максимална
разлика.
Вход
Първият ред на входния файл 2sec.in съдържа цяло положително число N, представляващо броя на ябълковите дървета. Вторият ред съдържа N цели числа, разделени с интервал, като i-тото число показва каква е печалбата от i-тото дърво.
Изход
Изходният файл 2sec.out трябва да съдържа единствен ред, на който е записана максималната разлика, която може да бъде получена според изискванията на Йон.
Ограничения
1 < N <
1001001
-128 <
печалбата от
всяко
отделно
дърво < 128
Пример
2sec.in |
2sec.out |
Обяснение |
10 |
21 |
8
-5 1 -3 7 -3 2
8 -3 1 |
Ограничение
за време: 0.5
секунди на
тест
Fechete Dan Ionut
University of Bucharest, Mathematics & IT Department
f.dan.ionut@gmail.com
Превод на
български:
Стоян Капралов