Submission #346881

#	Time	Username	Problem	Language	Result	Execution time	Memory
346881		BlancaHM	Bank (IZhO14_bank)	C++14	100 / 100	382 ms	86636 KiB

bank

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool posible(int indiceEmpleado, int mascara, vector<int> & salarios, vector<vector<int>> & formasDeLlegar, vector<vector<int>> & DP) {
	if (indiceEmpleado == (int) salarios.size())
		return true;
	if (DP[indiceEmpleado][mascara] != -1)
		return DP[indiceEmpleado][mascara];

	int salarioActual = salarios[indiceEmpleado];
	bool respuesta = false;
	for (auto posibilidad: formasDeLlegar[salarioActual]) {
		if (!(mascara & posibilidad)) {
			respuesta |= posible(indiceEmpleado + 1, mascara | posibilidad, salarios, formasDeLlegar, DP);
			if (respuesta)
				break;
		}
	}
	return DP[indiceEmpleado][mascara] = respuesta;
}

void mascarasASumas(vector<vector<int>> & formasDeLlegar, vector<int> & billetes, int mayorSalario) {
	int sumaActual, M = (int) billetes.size();
	for (int mascara = 0; mascara < (1<<M); mascara++) {
		sumaActual = 0;
		for (int i = 0; i < M; i++) {
			if (mascara & (1<<i))
				sumaActual += billetes[i];
		}
		if (sumaActual <= mayorSalario)
			formasDeLlegar[sumaActual].push_back(mascara);
	}
}

bool salariosAlcanzables(vector<int> & salarios, vector<vector<int>> & formasDeLlegar) {
	for (auto salario: salarios) {
		if (formasDeLlegar[salario].empty())
			return false;
	}
	return true;
}

int main() {
	int N, M, mayorSalario;
	vector<int> salarios, billetes;
	vector<vector<int>> formasDeLlegar;
	vector<vector<int>> DP;
	cin >> N >> M;
	salarios = vector<int>(N);
	billetes = vector<int>(M);
	DP.assign(N, vector<int>(1<<M, -1));

	for (int i = 0; i < N; i++)
		cin >> salarios[i];
	for (int i = 0; i < M; i++)
		cin >> billetes[i];
	mayorSalario = *max_element(salarios.begin(), salarios.end());
	formasDeLlegar = vector<vector<int>>(mayorSalario+1, vector<int>());
	mascarasASumas(formasDeLlegar, billetes, mayorSalario);

	if (salariosAlcanzables(salarios, formasDeLlegar) && posible(0, 0, salarios, formasDeLlegar, DP))
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool posible(int, int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
bank.cpp:21:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   21 |  return DP[indiceEmpleado][mascara] = respuesta;

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29