传送门

算法

DP。

用$f[i][j][k]$表示前i张卡片抽j张能否打出k。
注意到i最后是不需要的，可以压掉这一维。
状态转移方程即为$f[j]|=f[j-1]<<x[i]$，同时x也可以不开。
可以使用bitset来保存。

然后计算一下$t=0$时m的最小值和最大值即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
const int N=260;
const int M=75010;
const int INF=214748364;
int n,k,a,b;
bitset<M> f[N];
int l[M],r[M];
int main() {
    n=read(),k=read(),a=read(),b=read();
    f[0].set(0);
    int Sum=0;
    for (re int i=1;i<=n;i++) {
        int x=read();
        for (re int j=k;j;j--)
            f[j] |= f[j-1] << x;
        Sum+=x;
    }
    l[a]=-INF;
    for (re int i=a;~i;i--)
        if (f[k][i]) { l[a]=i; break; }
    for (re int i=a+1;i<=b;i++)
        if (f[k][i]) l[i]=i;
        else l[i]=l[i-1];
    r[b]=INF;
    for (re int i=b;i<=Sum;i++)
        if (f[k][i]) { r[b]=i; break; }
    for (re int i=b-1;i>=a;i--)
        if (f[k][i]) r[i]=i;
        else r[i]=r[i+1];
    int ans=-INF;
    for (re int i=a;i<=b;i++) ans=max(ans,min(i-l[i],r[i]-i));
    printf("%d\n",ans);
    return 0;
}