# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1138155 | Aliyyiakbar | Detecting Molecules (IOI16_molecules) | C++20 | 3 ms | 3656 KiB |
#include "molecules.h"
#include "bits/stdc++.h"
using namespace std;
vector<int> find_subset(int l, int r, vector<int> w)
{
int n = w.size();
vector<int> indices;
int sum = accumulate(w.begin(), w.end(), 0LL);
vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1));
vector<vector<int>> parent(n + 1, vector<int>(sum + 1, -1));
dp[0][0] = true;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= sum; ++j)
{
dp[i][j] = dp[i-1][j];
if (j >= w[i-1] && dp[i-1][j-w[i-1]])
{
dp[i][j] = true;
parent[i][j] = j - w[i-1];
}
}
}
for (int sm = l; sm <= r; ++sm)
{
if (dp[n][sm])
{
int current = sm;
for (int i = n; i > 0; --i)
{
if (parent[i][current] != -1)
{
indices.push_back(i-1);
current = parent[i][current];
}
}
return indices;
}
}
return {};
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |