传送门
这题是不是太sbsbsb了一点。
难度直逼普及-。
直接背包判存在性就行了。
代码:
#include<bits/stdc++.h>
using namespace std;
bool f[2][1005],tmp=0;
int ans=-1,n,bg,mx,x;
int main(){
scanf("%d%d%d",&n,&bg,&mx),f[0][bg]=1;
while(n--){
scanf("%d",&x),tmp^=1,memset(f[tmp],0,sizeof(f[tmp]));
for(int i=0;i<=mx;++i){
if(i-x>=0)f[tmp][i]|=f[tmp^1][i-x];
if(i+x<=mx)f[tmp][i]|=f[tmp^1][i+x];
}
}
for(int i=0;i<=mx;++i)if(f[tmp][i])ans=i;
cout<<ans;
return 0;
}