#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
vector<int>arm(vector<pair<int,int>>&dp,int j)
{
ll sig=j;
vector<int>ans;
while(sig>=0)
{
if(dp[sig].se>=0)
ans.pb(dp[sig].se);
sig=dp[sig].fr;
}
return ans;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
vector<int>ans;
if(l>u)
return ans;
vector<pair<int,int>>dp(u+1);
vector<bool>pos(u+1);
vector<pair<ll,ll>>v;
ll i, j;
for(i=0; i<sz(w); i++)
{
v.pb({w[i],i});
}
sort(all(v));
pos[0]=1;
dp[0].fr=-1;
dp[0].se=-1;
for(i=0; i<sz(v); i++)
{
ll x=v[i].fr;
int nod=v[i].se;
for(j=u; j>=x; j--)
{
if(pos[j])
continue;
if(pos[j-x])
{
pos[j]=1;
dp[j].fr=j-x;
dp[j].se=nod;
if(j>=l)
return arm(dp,j);
}
}
}
return ans;
}
Compilation message (stderr)
molecules.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | 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... |