This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<int> find_subset(int l, int u, vector<int> w)
{
sort(w.begin(),w.end());
int dp[(int)w.size()+1][u+1];
memset(dp,-1,sizeof dp);
int n=(int)w.size();
vector<int>arr;
int cap;
for(int idx=0;idx<=n;idx++)
{
for(cap=0;cap<=u;cap++)
{
if(idx==0 || cap==0)
{
dp[idx][cap]=0;
}
else
{
int nt=0+dp[idx-1][cap];
int t=0;
if(w[idx-1]<=cap)
{
t=w[idx-1]+dp[idx-1][cap-w[idx-1]];
}
dp[idx][cap]=max(nt,t);
}
}
}
int rez=dp[n][u];
if(rez<l || rez>u)
{
return {};
}
for(int i=n;i>0 && rez>0;i--)
{
if(rez==dp[i-1][cap])
{
continue;
}
arr.push_back(i-1);
rez-=w[i-1];
cap-=w[i-1];
}
return arr;
}
# | 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... |