# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1262979 | silentloop | Detecting Molecules (IOI16_molecules) | C++20 | 193 ms | 131072 KiB |
#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<vector<vector<int>>>&dp,int j)
{
ll sig=j, pos=dp[j][0][1];
vector<int>ans;
while(sig>=0)
{
if(dp[sig][pos][2]>=0)
ans.pb(dp[sig][pos][2]);
ll nS, nP;
nS=dp[sig][pos][0];
nP=dp[sig][pos][1];
sig=nS;
pos=nP;
}
return ans;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
vector<int>ans;
if(l>u)
return ans;
vector<vector<vector<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].pb({-1,-1,-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-x])
{
pos[j]=1;
vector<int>p={j-x,sz(dp[j-x])-1,nod};
dp[j].pb(p);
if(j>=l)
return arm(dp,j);
}
}
}
return ans;
}
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... |