Submission #1246314

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
bool dp[2][555555];
signed main(){
  int n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int s=0;
  for(int i=0;i<n;i++) s+=a[i];
  if(s<m){
    cout<<-1<<endl;
    return 0;
  }
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(int i=0;i<n;i++){
    bool f=i%2;
    for(int j=0;j<555555;j++) dp[!f][j]=0;
    for(int j=0;j<555555;j++){
      if(!dp[f][j]) continue;
      dp[!f][j]=1;
      if(j+a[i]<555555) dp[!f][j+a[i]]=1;
    }
  }
  int ans=s;
  for(int j=0;j<555555;j++){
    if(s-j>=m&&dp[n%2][j]) ans=s-j;
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result