Submission #936768

#TimeUsernameProblemLanguageResultExecution timeMemory
9367684QT0RDetecting Molecules (IOI16_molecules)C++17
0 / 100
1086 ms2488 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long pair<ll,ll> wej[200004]; bool taken[200004]; ll solve(ll l, ll p, ll ind){ ll val; if (l<=0){ if (p<0)return -1; return 0; } if (!ind)return -1; if (p-l>=wej[ind].first){ val=solve(l-wej[ind].first,p,ind-1); if (val<0)return -1; if (val+wej[ind].first>=l){ val+=wej[ind].first; taken[ind]=true; } return val; } else{ val=solve(l-wej[ind].first,p-wej[ind].first,ind-1); if (val>=0){ val+=wej[ind].first; taken[ind]=true; return val; } val=solve(l,p,ind-1); return val; } return -1; } vector<int> find_subset(int l, int u, vector<int> w){ ios_base::sync_with_stdio(0); cin.tie(0); ll n=w.size(); for (ll i = 1; i<=n; i++){ wej[i].first=w[i-1]; wej[i].second=i; } sort(wej+1,wej+n+1,greater<pair<ll,ll>>()); vector<int> ans; if (solve(l,u,n)>=0){ for (ll i = 1; i<=n; i++){ if (taken[i])ans.push_back(wej[i].second-1); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...