Python Problema do catálogo de livros em C++ e Python

[Gustavo Germano]

Boa noite . Alguém pode me ajudar como desenvolver esse problema, porém, na linguagem python? Abaixo está o problema e o código em C++

#include <bits/stdc++.h>
#define MAX 100
#define INF -1
#define ll long long int
using namespace std;

vector<ll> livros[MAX];
vector<ll> answer;

bool comp(int a, int b) { return a > b; }

int main() {

	ll n, x;
	for(int i = 0 ; i < 5; i++){
		scanf("%lld",&n);
		for(int j = 0; j <  n; j++)
		{
			scanf("%lld",&x);
			livros[i].push_back(x);
		}
	}

	for(int i = 0 ; i < livros[0].size(); i++)	
		for(int j = 0 ; j < livros[1].size(); j++)	
			for(int k = 0 ; k < livros[2].size(); k++)	
				for(int l = 0 ; l < livros[3].size(); l++)	
					for(int m = 0 ; m < livros[4].size(); m++)	
						answer.push_back(livros[0][i] + livros[1][j] + livros[2][k] + livros[3][l] + livros[4][m]);

	sort(answer.begin(),answer.end(),comp);

	scanf("%d",&n);
	ll res = 0;
	for(int k = 0 ; k < n; k++)
		res += answer[k];

	printf("%lld\n",res);
	return 0;
}

 

Bino tem vários conjuntos de diferente livros, onde cada conjunto representa uma matéria(português, matemática, física, química e biologia).  Sabendo o valor  de cada livro de uma certa matéria, sua tarefa é informar qual a soma dos valores dos K conjuntos distintos de livros mais valiosos. Onde um conjunto é definido por uma coleção de livros de cada matéria, e um conjunto é dito diferente se há pelo menos um livro diferente.

 

A entrada de forma resumida consiste em 6 linhas, as 5 primeiras definem respectivamente a coleção de livros de português, matemática, e assim por diante. Onde o primeiro inteiro n, é a quantidade de livros dessa matéria (1 <= n <= 5). E os demais n números que o seguem, (v1,v2,v3,…vi, onde i <= n e 1 <= vi <= 1000), são os valores de cada livro nessa coleção. A sexta linha contém apenas o inteiro K. O exemplo:
 

5 2 5 6 3 8

5 9 6 3 1 5

5 4 8 5 2 6

5 3 2 4 9 5

5 7 8 5 1 4

1

Qual nossa resposta para esse caso? Bem nesse caso é simples, como K é igual a 1, a pergunta que temos que responder é: Qual o maior valor possível de um conjunto formado por um livro de cada matéria? Basta colocarmos no nosso conjunto os maiores elementos de cada matéria.
Utilizaríamos os elementos pintados de verde, e assim nossa resposta seria 42.


5 2 5 6 3 8
5 9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
5 7 8 5 1 4
1

8 + 9 + 8 + 9 + 8 = 42.
 

Se K fosse 2. O conjunto em verde acima, seria o conjunto de maior valor, e o segundo conjunto de maior valor é o conjunto em amarelo abaixo, cuja soma é 41 logo a resposta é 42 + 41 = 83.

 

5 2 5 6 3 8

5 9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
5 7 8 5 1 4
1

 

8 + 9 + 8 + 9 + 7 = 41.

Certo, legal! Mas então quando K > 1  teremos que escolher algum elemento para tirar e colocar outro em seu lugar? E ir fazendo isso até que tenhamos a quantidade de K pedida, depois somamos tudo? SOCORROOOOO, isso ta parecendo muito complicado de codificar!
Como organizar quais já foram utilizados? Como saber quem tirar? O WA está batendo na nossa porta!

Então, como utilizar a ideia acima de forma mais simples?
Dica 1: sempre olhe o tamanho da entrada! Na maioria das vezes é isso quem vai dizer o quão eficiente sua resposta terá que ser.
Dica 2: pense!!!!!

Bem, seguindo a dica 1, perceba que n (quantidade de livros de uma certa matéria) é menor ou igual a 5. O que é bem pequeno, isso nos da a liberdade de fazer uma solução não tão eficiente sem medo de TLE. Ainda seguindo a dica 1, perceba no enunciado original da questão que “K (1 ≤ K ≤P*M*Q*F*B)”. O que faz sentido já que teremos que escolher um conjunto, do tipo: (p, m, q, f, b), onde p pertence ao conjunto de livros de português, m pertence ao conjunto de livros de matemática, … 

Certo, agora vamos pensar! Temos que escolher um p para colocar no conjunto, quantos livros de português podemos escolher? Bem, no máximo 5 (1 <= n <= 5). E essa resposta é a mesma para os demais livros já que para todos n vai até 5. Então quantos conjuntos diferentes existem no máximo?

5*5*5*5*5 = 5⁵ = 3125. Podemos gerar essa informação que passa no tempo!

Então sabemos que podemos testar todos os conjuntos sem medo de levar TLE, então agora basta implementar isso! Como fazemos?

for p in portugues:
   for m in matematica:
      for f in fisica:
          for q in quimica:
             for b in biologia:
                 (p + m + f + q + b) é um valor de um conjunto!

Como obter a resposta final? Podemos guardar a informação anterior (em uma lista por exemplo), ordená-la, e TCHANRAAAAM a resposta será a soma dos K maiores valores!