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.