Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2333

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2333

Pizza

 

Por OBI - Olimpíada Brasileira de Informática 2007 BR Brazil

Timelimit: 1

Rodrigo pediu uma pizza de mussarela de N fatias, uma parte somente com cebola e o resto somente com azeitonas. Entretanto, ao receber a pizza em casa, notou que o motoqueiro que a entregou não foi cuidadoso o suficiente, pois tanto as tiras de cebola quanto as azeitonas estavam espalhadas por toda a pizza. Para piorar, como a pizza era de mussarela, as tiras de cebola e as azeitonas estavam grudadas na pizza.

Como gosta mais de cebola do que de azeitona, Rodrigo deseja pegar fatias consecutivas da pizza de tal forma que estas contenham a maior diferença possível entre tiras de cebola e azeitonas. Para isso, ele contou quantas tiras e quantas azeitonas tinham em cada fatia e subtraiu os dois valores, nessa ordem. Assim, sempre que uma fatia contiver mais cebolas que azeitonas, ela recebe um número positivo, e caso contrário, um número negativo. Uma fatia cujo número seja zero contém o mesmo número de tiras de cebolas e azeitonas.

pizza

Por exemplo, supondo que as fatias contenham as seguintes diferenças: 5, −3, −3, 2, −1, 3, pode-se pegar uma fatia consecutiva com 9 cebolas a mais que azeitonas, utilizando as fatias com as diferenças 2, −1, 3, 5 (lembre-se de que estamos tratando de um círculo e, portanto, a fatia com diferença 5 é vizinha da fatia com diferença 3 e vice-versa).

Como Rodrigo não entende de programação, ele resolveu contar com seus serviços.

OBS: repare que é melhor não escolher nenhuma fatia caso somente seja possível escolher fatias consecutivas com mais azeitonas que cebolas.

Escreva um programa que, dados as diferenças entre as quantidades de cebolas e azeitonas em cada fatia de pizza, retorne a maior quantidade possível de cebolas que Rodrigo pode comer a mais do que a quantidade de azeitonas utilizando somente fatias consecutivas de pizza. (lembrando que a primeira fatia é adjacente à última e vice-versa).

 

Entrada

 

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N que indica o número de fatias de pizza (1 ≤ N ≤ 100.000). A segunda linha contém N inteiros K (−100 ≤ K ≤ 100) separados por um espaço em branco com as diferenças entre as quantidades de cebolas e de azeitonas.

 

Saída

 

Seu programa deve imprimir, na saída padrão, uma única linha, contendo a maior quantidade de cebolas que Rodrigo pode comer a mais do que azeitonas.

 

 

 

Exemplos de Entrada Exemplos de Saída

6

5 -3 -3 2 -1 3

9

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <map>
#define MAXN 100100
typedef long long ll;
ll vetor[MAXN], n;
ll max(ll x, ll y) {
    if (x > y) return x;
    return y;
}
int main() {
    scanf("%lld", &n);
    for (int i = 0; i  <  n; i++) scanf("%lld", &vetor[i]);
    ll maximo_ate_agora = 0LL, maximo_ate_aqui = 0LL, somavetor = 0LL,
       invertido_ate_agora = 0LL, invertido_ate_aqui = 0LL;
    for (int i = 0; i  <  n; i++) {
        maximo_ate_aqui = max(maximo_ate_aqui + vetor[i], 0);
        maximo_ate_agora = max(maximo_ate_agora, maximo_ate_aqui);
        somavetor += vetor[i];
    }
    for (int i = 0; i  <  n; i++) {
        invertido_ate_aqui = max(invertido_ate_aqui - vetor[i], 0);
        invertido_ate_agora = max(invertido_ate_agora, invertido_ate_aqui);
    }
    printf("%lld\n", max(maximo_ate_agora, invertido_ate_agora + somavetor));
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6
5 -3 -3 2 -1 3

Output

x
+
cmd
9
Advertisements

Demonstration


Previous
#2332 Beecrowd Online Judge Solution 2332 Jogo do Labirinto Solution in C, C++, Java, Js and Python
Next
#2339 Beecrowd Online Judge Solution 2339 Aviões de Papel Solution in C, C++, Java, Js and Python