# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1165053 | chikien2009 | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
// inline void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// }
vector<int> find_subset(short l, short u, vector<int> w)
{
queue<short> q;
vector<int> res,
vector<short> p[w.size()];
short sum = 0, x = -1;
for (short i = 0; i < w.size(); ++i)
{
p[i].resize(u + 1);
for (short j = 0; j <= u; ++j)
{
p[i][j] = (i == 0 ? -1 : p[i - 1][j]);
}
for (short j = u; j >= w[i]; --j)
{
if (p[i][j - w[i]] != -1 || j == w[i])
{
p[i][j] = i;
if (l <= j && x == -1)
{
x = j;
}
}
}
}
for (short i = w.size() - 1, j; i >= 0 && x > 0;)
{
j = p[i][x];
res.push_back(p[i][x]);
while (0 <= i && p[i][x] == res.back())
{
i--;
}
x -= w[res.back()];
}
reverse(res.begin(), res.end());
return res;
}
// short main()
// {
// setup();
// short n, u, l;
// vector<short> v;
// cin >> n >> l >> u;
// v.resize(n);
// for (short i = 0; i < n; ++i)
// {
// cin >> v[i];
// }
// v = find_subset(l, u, v);
// for (auto & i : v)
// {
// cout << i << " ";
// }
// return 0;
// }