Fișierul intrare/ieșire | expresie3.in, expresie3.out | Sursă | OJI 2009 clasa a 9-a |
---|---|---|---|
Autor | Alin Burță | Adăugată de | Teodor Plop • teodor94 |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 512 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Expresie3 (clasa a 9-a)
Această problemă este o extindere a problemei expresie, având restricțiile schimbate.
Costel are de rezolvat o temă grea la matematică: având la dispoziție N numere naturale nenule trebuie să așeze între acestea 2 operații de înmulțire și N – 3 operații de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date. De exemplu, dacă N = 5 și numerele sunt 4, 7, 1, 5, 3, operațiile pot fi așezate 4 + 7 * 1 + 5 * 3, 4 * 7 * 1 + 5 + 3 etc.
Cerință
Scrieți un program care să așeze două operații de înmulțire și N – 3 operații de adunare între cele N valori date astfel încât valoarea expresiei obținute să fie maximă.
Date de intrare
Fișierul de intrare expresie3.in va contine pe prima linie un număr natural N, reprezentând numărul elementelor date. Pe următoarele linii se află cele N numere naturale date, fiecare pe câte o linie.
Date de ieșire
Fișierul de ieșire expresie3.out va conține, pe prima linie, valoarea maximă obținută prin evaluarea expresiei
Restricții
- 4 ≤ N ≤ 150.000
- Numerele date sunt numere naturale între 1 și 10.000
Exemplu
expresie3.in | expresie3.out |
---|---|
5 4 7 1 5 3 |
44 |
Explicație
Valoarea maximă se obține prin așezarea operațiilor sub forma: 4 * 7 + 1 + 5 * 3