S2 - Súčin 2Časový limit: 15s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]
ÚlohaPaulínka sa na hodine matematiky nudí (teraz preberajú násobenie čísel, ktoré už dávno vie). Keďže má so sebou hracie karty s číselnými hodnotami, rozhodla si zahrať hru, kde z balíčka kariet bude brať karty postupne z jedného z koncov. Hodnotu karty vynásobí počtom kariet, ktoré už z balíčka zobrala. Po pár hrách už začala premýšľať, v akom poradí má jednotlivé karty brať, aby na konci získala najväčší súčet takto vzniknutých súčinov.Pomôžte jej napísať program, ktorý pre zadané poradie kariet v balíčku, nájde najlepšie možné riešenie. Vstup N2Prvý riadok vstupu obsahuje počet testovacích sád. Každá testovacia sada pozostáva z dvoch riadkov: Prvý riadok obsahuje jedno celé číslo N (1 ≤ N ≤ 2 000) – počet kariet. Druhý riadok obsahuje N celých čísel oddelených medzerami, hodnoty i-tej karty hi (1 ≤ hi ≤ 1 000) .Výstup N2Výstupom je jeden riadok pre každú testovaciu sadu obsahujúci jedno kladné číslo reprezentujúce najlepší výsledok podľa zadania.PríkladVstup:1 5 1 3 1 5 2 Výstup43 PoznámkaKarty v príklade sú zobrazené na obrázku (1-3-1-5-2). Pri výbere kariet z krajov v poradí s hodnotami 1, 2, 3, 1, 5 dostávame súčiny 1, 4, 9, 4, 25 s celkovým súčtom 43. |