bzoj 2748

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1005;
 4 int dp[55][1010];
 5 
 6 int main(){
 7     int n,s,e;
 8     cin>>n>>s>>e;
 9     dp[0][s]=1;
10     int x;
11     for(int i=1;i<=n;i++){
12         scanf("%d",&x);
13         for(int j=e;j>=0;j--){
14             if(j-x<0) break;
15             if(dp[i-1][j]){
16                 dp[i][j-x]=1;
17             }
18         }
19         for(int j=0;j<=e;j++){
20             if(j+x>e) break;
21             if(dp[i-1][j])
22                 dp[i][j+x]=1;
23         }
24     }
25     int t=0;
26     for(int i=e;i>=0;i--){
27         if(dp[n][i]){
28             t=1;cout<<i<<endl;break;
29         }
30     }
31     if(!t) cout<<-1<<endl;
32     return 0;
33 }