#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<pair<int,int>>&dp,int j)
{
ll sig=j;
vector<int>ans;
while(sig>=0)
{
if(dp[sig].se>=0)
ans.pb(dp[sig].se);
sig=dp[sig].fr;
}
return ans;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
vector<int>ans;
if(l>u)
return ans;
vector<pair<int,int>>dp(u+1);
vector<bool>pos(u+1);
vector<pair<ll,ll>>v;
ll i, j, mi=LLONG_MAX, sum=0;
for(i=0; i<sz(w); i++)
{
if(w[i]>u)
continue;
mi=min(mi,1ll*w[i]);
v.pb({w[i],i});
sum=sum+w[i];
if(l<=w[i]&&w[i]<=u)
{
ans.pb(i);
return ans;
}
}
if(mi>u||sum<1ll*l)
return ans;
sort(all(v));
pos[0]=1;
dp[0].fr=-1;
dp[0].se=-1;
set<ll>s;
s.insert(0);
for(i=0; i<sz(v); i++)
{
ll x=v[i].fr;
int nod=v[i].se;
auto it=s.upper_bound(u-x);
vector<ll>in;
while(it!=s.begin())
{
it=prev(it);
j=*it;
if(pos[j+x])
continue;
pos[j+x]=1;
dp[j+x].fr=j;
dp[j+x].se=nod;
in.pb(j+x);
if(j+x>=l)
return arm(dp,j+x);
}
for(auto k:in)
s.insert(k);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
molecules.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | 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... |