루미 알고리즘

#1452플래티넘Frukostbuffé

PO 2018 온라인 예선코딩출제 Emanuel Gedin스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Pär och Oskar ska äta frukostbuffé. Den består av N olika rätter numrerade från 1 till N. Dessa är placerade på rad på ett långt bord. Pär tycker att vissa rätter är godare än andra. Därför har han gett varje rätt ett betyg som beskriver hur god den är. Den i:te rätten har betyg a_i.

I början väljer Pär en rätt och äter den. Sedan väljer Oskar en rätt och äter den. Båda är mycket hungriga, så de äter alltid upp allt som finns av sin valda rätt.

När båda har ätit upp får de välja en ny rätt. Pär och Oskar tycker att det är jobbigt att gå så de väljer alltid en rätt som är precis bredvid den de just åt. D.v.s., om någon just ätit rätt i kan han välja rätt i-1 eller i+1. Om den nya rätten inte är uppäten tar den som valde den och äter den. Om den redan är uppäten måste personen vänta till nästa tur. I varje tur är det Pär som väljer först.

Pär vill inte vara kräsen, så han tänker inte gå förbi en rätt som finns kvar utan att äta den. Han är också som sagt mycket hungrig, så han vill alltid äta minst en rätt. Både Pär och Oskar har efter att ha ätit en rätt möjligheten att högt utropa "Nu är jag mätt!" och lämna frukosten utan att äta något mer.

Frukosten är slut när alla rätter är uppätna eller båda har lämnat frukosten. Hur nöjd Per är beror på hur goda rätter han har ätit. Vi definierar hans nöjdhet som summan av betygen av alla rätter han åt.

Pär vet inte riktigt hur Oskar kommer att bete sig. Därför vill han veta vilken maximala nöjdhet han kan garantera sig utan att veta något om Oskars beteende.

Indata

Den första raden innehåller ett heltal N (2 ≤ N ≤ 3*10^5), antalet rätter i buffén. Därefter följer en rad med N stycken heltal a_1, a_2, …, a_i (-100 ≤ a_i ≤ 100), godheten på den i:te rätten.

Utdata

Programmet ska skriva ut ett heltal: den maximala nöjdhet Pär garanterat kan få.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängGränser
1252 ≤ N ≤ 100, 0 ≤ a_i ≤ 100
2252 ≤ N ≤ 1000, 0 ≤ a_i ≤ 100
3250 ≤ a_i ≤ 100
425Inga ytterligare begränsningar

Förklaring av sample

Sample 1

Om Pär väljer att börja med att äta någon av rätterna som ger 3 eller 2 skulle Oskar kunna äta upp all annan mat. Därför vill Pär istället börja i mitten, och kan då garanterat uppnå nöjdhet 7.

Sample 2

Bäst här är för Pär att börja med att välja rätten som ger 5. Beroende på vilken sida Oskar börjar på så kan Pär få antingen 8 eller 9 nöjdhet, alltså garanterat 8.

Sample 3

I den sista testfallsgruppen kan rätter vara dåliga, och ge negativ nöjdhet. Även här är det bäst för Pär att börja på rätten som ger 5. Börjar Oskar till vänster om honom så kan Pär äta rätten som ger -1 och sedan den som ger 2, för en total nöjdhet på 6. Om Oskar börjar till höger om honom kan Pär äta -2, 3 och sedan vara nöjd, även det för en total nöjdhet på 6.

Sample 4

Här är alla rätter dåliga, men Pär måste ändå äta något. Därför väljer han den minst dåliga rätten, och får nöjdhet -1.

예제

예제 1

입력
3
3 5 2
출력
7

예제 2

입력
5
3 5 2 1 2
출력
8

예제 3

입력
6
-1 3 -2 5 -1 2
출력
6

예제 4

입력
3
-1 -2 -3
출력
-1

출처 표기

출처: Programmeringsolympiaden 2018년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.