제출 #725443

#제출 시각아이디문제언어결과실행 시간메모리
725443AndrijaMDetecting Molecules (IOI16_molecules)C++14
0 / 100
1 ms212 KiB
#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]<=cap) { t=w[idx]+dp[idx-1][cap-w[idx]]; } dp[idx][cap]=max(nt,t); } } } int rez=dp[n][u]; for(int i=n;i>0 && rez>0;i--) { if(rez==dp[i-1][cap]) { continue; } else { arr.push_back(i-1); rez-=w[i-1]; cap-=w[i-1]; } } return arr; }
#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...