스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Grupp | Poängvärde | Gränser |
| 1 | 32 | 1 ≤ n ≤ 1000 |
| 2 | 12 | Sekvensen a_1 … a_n är icke-sjunkande. |
| 3 | 11 | Sekvensen a_1 … a_n är icke-ökande. |
| 4 | 45 | Inga 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