루미 알고리즘

#1439골드Fluortanten

PO 2018 결선코딩출제 Fredrik Hernqvist스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Björn och n-1 andra personer står i kön för att träffa fluortanten. Olika personer tycker att det är olika läskigt att träffa fluortanten. Personerna är numrerade från 1 till n, och person i står på plats i i kön. Person i har också ett värde a_i, som visar hur ogärna personen vill träffa fluortanten. Person i:s glädje över sin plats i kön är i · a_i. Vissa personer kan ha negativ a_i, vilket betyder att de egentligen vill träffa fluortanten och sålunda är ledsna över att få vänta.

Björn är den enda personen som är helt likgiltig inför att träffa fluortanten, det vill säga han är den enda personen som har a_i = 0. Dessutom är han väldigt godhjärtad, så han bestämmer sig för att lämna kön och sedan gå in i kön igen på någon plats så att den totala glädjen hos alla i kön blir så stor som möjligt. Skriv ett program som givet värdena a_i för alla personer räknar ut den maximala summan av glädjen i kön om Björn ställer sig på en optimal plats.

Indata

Den första raden innehåller ett heltal n (1 ≤ n ≤ 10^6), antalet personer i kön. På nästa rad följer n heltal, där det i:te talet, -1000 ≤ a_i ≤ 1000, beskriver glädjen hos den i:te personen i kön.

Utdata

Skriv ut ett heltal: den maximala totala glädjen i kön.

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ängvärdeGränser
1321 ≤ n ≤ 1000
212Sekvensen a_1 … a_n är icke-sjunkande.
311Sekvensen a_1 … a_n är icke-ökande.
445Inga ytterligare begränsningar.

Förklaring av exempel 1

Björn ställer sig sist i kön. Summan av glädjen blir då 1 · 1 + 2 · (-2) + 3 · 0 = -3.

Om Björn i stället ställt sig först i kön hade summan av glädje blivit 1 · 0 + 2 · 1 + 3 · (-2) = -4, och i mitten hade den blivit 1 · 1 + 2 · 0 + 3 · (-2) = -5. Båda dessa är sämre alternativ.

예제

예제 1

입력
3
1 0 -2
출력
-3

예제 2

입력
5
0 -8 1 1 5
출력
24

예제 3

입력
7
2 -4 5 -3 0 -1 2
출력
7

출처 표기

출처: 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.