#43 Exercício - Mário

Nome: Mário
Link: http://br.spoj.pl/problems/MARIO/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.90
Memória usada: 4.1M
Colocação alcançada: 100+
Tentativas: 5

Comentário:
Parece besteira, mas eu levei um tempão pra resolver graças a um detalhe que foi pura preguiça minha de ler o enunciado e consertar.
Esse exercício pode parecer complexo, porém eu acabei encontrando uma solução bem simples, inclusive parecida com um exercício que eu resolvi esses dias, o Bolo de apostas.
Acontece que eu usei algo parecido com o max interval sum, e acabei resolvendo o problema. Recomendo que estudem para ter uma ideia do que estou falando.
Aliás, usem a criatividade. As vezes dá pra fazer muito com pouco...

Dicas:
- Estudem o algoritmo max interval sum e adaptem-o a este problema.
- Tomem cuidado com o tamanho das entradas, que podem ser de até 1 bilhão, por mais que sejam somente 100 mil armários.

Casos de teste úteis


Entrada:
7 7
1 8 10 20 30 40 50
6 7
1 2 5 6 8 9 10
10 20
5 7 9 10 11 15 16 17 20 21 22 23 24 30 31 32 33 35 37 39
0 0

Saída:
5
1
2