Solução Plantação

Código de Roger Benet, comentários de Rogério Júnior

Vamos simular o problema, ordenando as árvores por suas quantidades iniciais de frutos, para retirarmos as mortas de maneira eficiente.

Seja $$vet[100100]$$ o vetor em que guardaremos quantos frutos cada árvore deu no dia anterior ao início da safra. Ordenaremos $$vet$$ e simularemos cada dia da safra. Em cada dia, $$sm$$ será a soma de todos os frutos dados no dia anterior ao início da safra por todas as árvores que ainda estão vivas, $$qtd$$ será a quantidade de árvores vivas, $$mini$$ será a posição em $$vet$$ da menor árvore que ainda está viva e $$d$$ é quantos frutos, a mais ou a menos, cada árvore dará em relação a como começou a safra.

Seja $$res$$ a resposta do problema (deveremos salvá-la como $$long$$ $$long$$). Para simularmos um dia da safra, primeiro leremos o caractere que diz se houve chuva ou estiagem. Se tiver chovido, todas as árvores vivas darão um fruto a mais, ou seja, o valor de $$d$$ aumentará em uma unidade. Se, porém, houver estiagem, todas as árvores vivas produzirão um fruto a menos, logo o valor de $$d$$ decresce em uma unidade. Se $$d<0$$ alguma árvore pode ter morrido. Como o número de frutos que a árvore $$i$$ dá é $$vet[i]+d$$, uma árvore terá morrido neste dia se $$vet[i]=-d$$. Sabendo isso, procuraremos em $$vet$$ as árvores que já morreram. Partindo da árvore viva que está dando menos frutos (a da posição $$mini$$) para a direita, se a árvore que estamos olhando tiver morrido, o valor de $$qtd$$ diminui uma unidade, o de $$mini$$ aumenta uma unidade (pois agora a árvore viva com menos frutos está uma posição à direita) e subtraímos a sua quantidade original de frutos do valor de $$sm$$, visto que esta soma é apenas para árvores vivas. Se a árvore não tiver morrido, não precisaremos procurar mais, pois todas à sua direita têm mais frutos que ela. No fim do dia, adicionamos a $$resp$$ a colheita do dia, que será $$sm+d\times qtd$$.

Após a simulação, basta imprimirmos o valor de $$resp$$. Segue o código adaptado do nosso leitor Roger Benet como solução para o problema proposto.