All Tracks Data Structures Arrays 1-D Problem

Bela Jornada
/

Data Structures, One-dimensional

Problem
Editorial
Analytics

A BR-101 (Também chamada de Translitorânea, oficialmente nomeada Rodovia Governador Mário Covas) é uma estrada longitudinal do Brasil. É a mais longa do país.

enter image description here

A estrada tem N checkpoints. Cada checkpoint tem um valor de beleza denotado como um array A em ordem do ínício da estrada até o final da mesma. O valor de beleza de um checkpoint consiste na beleza dos lugares próximos ao checkpoint. Você está planejando viajar pela estrada. Como é uma longa estrada, você irá parar em um dos checkpoints para um pouco de descanso e após este descanso, contiuar sua jornada.

Então, sua jornada em dois sub-arrays próximos, \(S_1\) sendo os checkpoints antes de seu descanso (incluindo o que você irá parar) e \(S_2\) sendo os checkpoints depois de seu descanso, tal que \(tamanho(S_1) + tamanho(S_2) = N\) (i.e. todo checkpoint pertence a um exato sub-array).

A beleza total da jornada é definida por \(soma(S_1) * soma(S_2)\) onde \(soma(S)\) é a soma total do valor de beleza no sub-array S. Você quer maximizar o valor de \(soma(S_1) * soma(S_2)\).

Entrada

A primeira linha de entrada contém um inteiro \(N (2 \le N \le 10^5)\), denotando o número de checkpoints. A segunda linha contém N inteiros separados, denotando o valor de beleza dos checkpoints \((1 \le A_i \le 10^4 )\).

Saída

Você tem que apresentar o valor maximo de \(soma(S_1) * soma(S_2)\).

SAMPLE INPUT
5
1 2 3 4 5
SAMPLE OUTPUT
54
Explanation

\(soma(s1) ∗ soma(s2)\) irá ser o máximo quando \(s_1 = [1, 2, 3]\) e \(s_2 = [4, 5]\). \(soma(s_1) = 6\) e \(soma(s_2) = 9\), então \(soma(s_1) ∗ soma(s_2) = 54\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?