Submission #2559878

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
typedef vector<pii> vpii;
using namespace std;

int main(){
  ll N; cin>>N;
  vi A(N); REP(i,N) cin>>A[i];
  bitset<2000*2000+1> bs(1);
  REP(i,N){
    bs|=(bs<<A[i]);
  }
  ll sum=0; REP(i,N) sum+=A[i];
  for(ll i=(sum+1)/2;true;i++){
    if(bs[i]){
      cout<<i<<endl;
      return 0;
    }
  }
}

Submission Info

Judge Result