只考虑第一问，将珠子按照价值从小到大排序，设排序后第$i$小的为$b[i]$，定义二元组$(x,y)$表示当前珠子的总价值为$x$，用的价值最大的珠子为$y$，用一个小根堆来维护所有状态。一开始往堆中加入$(b[1],1)$状态，然后每次取出堆顶元素$(x,y)$，可以扩展出$(x+b[y+1],y+1)$以及$(x-b[y]+b[y+1],y+1)$两个状态。如此重复，直至取满$k$个。这部分的时间复杂度为$O(k\log k)$。
对于第二问，设第一问的答案为$limit$，然后按字典序进行爆搜，假设当前可以在$[l,n]$里选一个珠子加入，那么总和不能超过$limit$，可以通过若干次在线段树上二分找到所有这样的点。因为加上这个剪枝后，只会遍历到$k$个状态，所以这部分复杂度为$O(k\log n)$。
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 1000010
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
int n,k,i,a[N],b[N],ret,q[N],t,v[2100000];ll f[N];
priority_queue<P,vector<P>,greater<P> >Q;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
void build(int x,int a,int b){
if(a==b){v[x]=::a[a];return;}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b),v[x]=min(v[x<<1],v[x<<1|1]);
}
int ask(int x,int a,int b,int c,ll p){
if(c<=a){
if(v[x]>p)return 0;
if(a==b)return a;
}
int mid=(a+b)>>1;
if(c<=mid){
int t=ask(x<<1,a,mid,c,p);
if(t)return t;
}
return ask(x<<1|1,mid+1,b,c,p);
}
void dfs(int x,ll s){
if(!ret)return;
if(!s){
if(!(--ret))for(int i=1;i<=t;i++)printf("%d ",q[i]);
return;
}
for(;x<=n;x++){
x=ask(1,1,n,x,s);
if(!x)return;
q[++t]=x;
dfs(x+1,s-a[x]);
t--;
}
}
int main(){
read(n),read(k);k--;
if(!k)return puts("0"),0;
for(i=1;i<=n;i++)read(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
Q.push(P(b[1],1));
for(i=1;i<=k;i++){
P t=Q.top();Q.pop();f[i]=t.first;
if(t.second==n)continue;
Q.push(P(t.first+b[t.second+1],t.second+1));
Q.push(P(t.first-b[t.second]+b[t.second+1],t.second+1));
}
printf("%lld\n",f[k]);
for(i=k;f[i]==f[k];i--);
ret=k-i;
build(1,1,n);
dfs(1,f[k]);
return 0;
}