Solução escrita por Malu Azevedo
Conhecimentos necessários:
O problema nos pede para determinar a menor pontuação possível que o amigo posicionado em cada prédio $i$ consegue atingir ao fotografar exatamente $F_i$ prédios à sua direita que não estejam cobertos por prédios mais altos, ou imprimir $-1$ caso o amigo não consiga tirar a quantidade exigida de fotos.
Ideia Central
Como cada pessoa só consegue fotografar os prédios à sua direita que estão visíveis (ou seja, não bloqueados por nenhum prédio intermediário de altura maior ou igual), precisamos de uma estrutura que mantenha o histórico dos prédios válidos de forma organizada. Processando os prédios da direita para a esquerda (em ordem reversa), podemos utilizar uma pilha monotônica. Essa pilha armazena dinamicamente apenas os prédios que permanecem visíveis, garantindo que suas alturas formem uma ordem decrescente, pois qualquer prédio menor ou igual a uma nova estrutura à esquerda fica permanentemente encoberto.
Abordagem Completa
Percorremos os prédios do fim para o início (de $N-1$ até $0$). Para cada prédio $i$, os prédios visíveis à sua direita estão guardados na pilha. Verificamos primeiro se a quantidade de elementos disponíveis na pilha é menor do que $F_i$, caso seja, o amigo não tem prédios suficientes para fotografar e registramos $-1$.
Caso contrário, precisamos calcular a pontuação, que é a soma ponderada das alturas dos prédios fotografados multiplicada pela posição da foto ($1 \times A_{foto_1} + 2 \times A_{foto_2} + \dots$). Para calcular essa faixa de forma instantânea sem precisar de loops internos (o que geraria uma complexidade quadrática ruim), utilizamos vetores de somas de prefixos (somaponderada e somaacumulada). Isso nos permite obter o resultado exato em tempo constante $O(1)$ por prédio.
Por fim, antes de avançar para o próximo prédio à esquerda, limpamos da pilha todos os prédios que são menores ou iguais à altura atual (já que o prédio $i$ vai encobri-los para quem está mais à esquerda) e inserimos o prédio $i$ no topo. A complexidade final é $O(N)$.