# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1211751 | ASGA_RedSea | Detecting Molecules (IOI16_molecules) | C++17 | 0 ms | 328 KiB |
/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int>find_subset(int l,int r,vector<int>a){
vector<ll>w(a.begin(),a.end());
if(accumulate(w.begin(),w.end(),0LL)<l)return {};
int n=a.size();
vector<vector<int>>f(r+1);
for(int i=0;i<n;i++){
if(a[i]<=r){
f[a[i]].push_back(i);
}
}
sort(a.rbegin(),a.rend());
vector<int>d(r+1,-1);
d[0]=0;
int mx=0;
for(int&i:a){
for(int j=r;j>=i;j--){
if(d[j-i]!=-1){
d[j]=j-i;
mx=max(mx,j);
}
}
if(mx>=l)break;
}
if(mx<l)return {};
vector<int>ret;
ll tot=0;
int mmx=mx;
while(mx>0){
assert(d[mx]!=-1&&d[d[mx]]!=-1);
ret.push_back(f[mx-d[mx]].back());
f[mx-d[mx]].pop_back();
mx=d[mx];
}
for(int&i:ret)tot+=w[i];
//assert(tot==mmx);
return ret;
}
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... |