Submission #290495

#	Time	Username	Problem	Language	Result	Execution time	Memory
290495		aymanrs	Detecting Molecules (IOI16_molecules)	C++14	31 / 100	48 ms	65540 KiB

molecules

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dp;
vector<int> mA;
int best = 0;
int solve(int u, const vector<int>& w, int l, vector<int>& taken){
	if(l < 0 || u <= 0) return 0;
	if(dp[l][u] != -1) return dp[l][u];
	auto copy = taken;
	dp[l][u] = solve(u, w, l-1, taken);
	int alt = -1;
	if(w[l] <= u){
		copy.push_back(l);
		alt = w[l] + solve(u - w[l], w, l-1, copy);
	}
	if(alt > dp[l][u]) {
		dp[l][u] = alt;
		taken = copy;
	}
	if(dp[l][u] > best){
		best = dp[l][u];
		mA = taken;
	}
	return dp[l][u];
}
vector<int> find_subset(int l, int u, vector<int> w){
	dp = vector<vector<int>>(w.size(), vector<int>(u+1, -1));
	vector<int> taken;
	solve(u, w, w.size() - 1, taken);
	if(best < l){
		return {};
	}
	return mA;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31