Problem: Example

Input

4 2 58 100
10 10 50 80


Output

75
2 3

Solution (in CPP):

Solution:
bool debug=false;
#include <stdio.h>
#include <vector>
#include <bitset>
#include <utility>
using namespace std;
#define PB push_back
#define F first
#define S second
const int N=6e2+10;
const int S=2e5+10;
int myabs(int n){return n>0?n:-n;}
short min(short a,short b){return a>b?b:a;}
short max(short a,short b){return a>b?a:b;}
short dp[2][N][S],from[2][N][S],x[N];
int main(){
    bitset<N> bs;
    short n,k,nxt;
    int apos=0,pos,ans=0,dis=-1,temp,npos=0,a,b,tot=0;
    pair<short,pair<short,int>> now;
    vector<int> v;
    scanf("%hd%hd%d%d",&n,&k,&a,&b);    
    for(int i=1;i<=n;i++)scanf("%hd",&x[i]);
    for(int i=1;i<=k;i++)tot+=x[i];
    for(int i=0;i<=n;i++)for(int j=0;j<S;j++)dp[0][i][j]=dp[1][i][j]=k+1;
    dp[0][k][tot]=0;
    if(debug)printf("before dp\n");
    for(int i=k;i<=n;i++){
        for(int j=0;j<S;j++)if(dp[1][i][j]<=k)for(int p=dp[1][i][j]+1;p<=min(dp[1][i-1][j],k);p++)if(dp[0][i][j-x[p]]>p){
                from[0][i][j-x[p]]=i+2000;
                dp[0][i][j-x[p]]=p;
                if(debug)printf("dp[0][%d][%d]=%d (from dp[%d][%d][%d])\n",i,j-x[p],p,1,i,j);
        }
        for(int j=0;j<S;j++)if(dp[0][i][j]<=k){
            if(dp[0][i+1][j]>dp[0][i][j]){
                dp[0][i+1][j]=dp[0][i][j];
                from[0][i+1][j]=i+1000;
                if(debug)printf("dp[0][%d][%d]=%d (from dp[%d][%d][%d])\n",i+1,j,dp[0][i+1][j],0,i,j);
            }
            if(dp[1][i+1][j+x[i+1]]>dp[0][i][j]){
                dp[1][i+1][j+x[i+1]]=dp[0][i][j];
                from[1][i+1][j+x[i+1]]=i;
                if(debug)printf("dp[1][%d][%d]=%d (from dp[%d][%d][%d])\n",i+1,j+x[i+1],dp[1][i+1][j+x[i+1]],0,i,j);
            }
        }
    }
    if(debug)printf("after dp\n");
    for(int i=0;i<S;i++)if(dp[0][n][i]<=k)v.PB(i);
    if(debug){
        printf("%d",v[0]);
        for(int i=1;i<v.size();i++)printf(" %d",v[i]);
        printf("\n");
    }
    for(int i=a;i<=b;i++){
        temp=S;
        while(npos<v.size()){
            if(v[npos]<i)npos++;
            else break;
        }
        if(npos>=v.size())pos=v.back();
        else if(npos==0)pos=v[npos];
        else if(v[npos]-i>i-v[npos-1])pos=v[npos-1];
        else pos=v[npos];
        if(dis<myabs(i-pos)){
            dis=myabs(i-pos);
            ans=i;
            apos=pos;
        }
    }
    printf("%d\n",ans);
    now={0,{n,apos}};
    bs.reset();
    for(int i=1;i<=k;i++)bs[i]=true;
    while(now.S.F>k){
        if(debug)printf("now=(%hd,%hd,%d)\n",now.F,now.S.F,now.S.S);
        nxt=from[now.F][now.S.F][now.S.S];
        if(nxt>=2000){
			nxt-=2000;
            bs[dp[now.F][now.S.F][now.S.S]]=false;
            now={1,{nxt,now.S.S+x[dp[now.F][now.S.F][now.S.S]]}};
        }
        else if(nxt>=1000)now={0,{nxt-1000,now.S.S}};
        else {
            bs[now.S.F]=true;
            now={0,{now.S.F-1,now.S.S-x[now.S.F]}};
        }
    }
    v.clear();
    for(int i=1;i<=n;i++)if(bs[i])v.PB(i);
    printf("%d",v[0]);
    for(int i=1;i<k;i++)printf(" %d",v[i]);
    printf("\n");
}