Solução por Samyra Almeida
Conhecimentos prévios necessários:
- Sweep line
- BIT (Binary Indexed Tree, também conhecida como Árvore de Fenwick)
- Compressão de coordenadas
Chame de $$S = \{S_1, S_2, S_3 …, S_{K-1}, S_K\}$$ como a melhor lista de convidados. Por hora, vamos ignorar o quanto cada um pode doar. Segundo o enunciado do problema podemos concluir, para o conjunto $$S$$, que:
- $$B_1 \leq B_2 \leq B_3 \leq … \leq B_{K-1} \leq B_K$$
- $$F_1 \leq F_2 \leq F_3 \leq … \leq F_{K-1} \leq F_K$$
Agora ordenaremos todos os candidatos em ordem crescente de beleza e em caso de empate o candidato com maior fortuna virá primeiro. Após isso, iremos realizar uma compressão de coordenadas nos valores de beleza e fortuna de todos os candidatos. Ao final da compressão, iremos juntar as doações de todos os candidatos que possuem a mesma beleza e a mesma fortuna, simultaneamente, pois eles sempre poderão ser convidados juntos.
Chame de $$U_{i_f} =$$ fortuna do $$U_i$$ candidato, $$U_{i_b} =$$ beleza do $$U_i$$ candidato e $$U_{i_d} =$$ doação do $$U_i$$ candidato.
Agora, depois de comprimirmos nossa lista de candidatos, iremos processá-la. Para o $$U_i$$ candidato, iremos consultar na BIT a $$query(U_{i_f} – 1)$$, ou seja, a maior doação que pode ser feita utilizando somente os candidatos que possuem uma fortuna menor que $$U_{i_f}$$. Como os candidatos já estão em ordem crescente de beleza e decrescente de fortuna, não precisamos nos preocupar que a resposta do $$U_i$$ contenha algum candidato com maior beleza e/ou menor fortuna, pois estes ainda não foram processados.
Após isso, iremos atualizar nossa resposta para o máximo entre a resposta anterior e $$query(U_{i_f} – 1) + U_{i_d}$$. Por fim, iremos fazer $$update(U_{i_f}, query(U_{i_f} – 1) + U_{i_d})$$, ou seja, adicionamos a resposta do $$U_i$$ candidato na BIT.
Ao final, basta imprimir a resposta. Segue o código solução:
https://gist.github.com/samyravitoria/293ab30365d1a0725f63a157fd2b2f7c