Fișierul intrare/ieșire expresie3.in, expresie3.out Sursă OJI 2009 clasa a 9-a
Autor Alin Burță Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.2 sec Limită de memorie 512 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii