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 
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.
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;
}
Input
5 -3 -3 2 -1 3
Output