Submission #158001

---

Source Code Expand

#include <bits/stdc++.h>
 
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lli long long int
#define foreach( gg,itit )	for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )
#define FM( ii,aa,bb ) for( int ii=aa;ii>=bb;ii-- )
 
using namespace std;
 
int q,n,m,arr[50000],s[155],dp[150005];
 
int main(){
	int tree=0;
	cin >> q >> n >> m;
	FP( i,1,n ){
		cin >> arr[i];
		tree += arr[i];
	}
	int maxi=0;
	dp[0] = 1;
	FP( i,1,n ){
		FM( j,q,arr[i] )
			if( dp[j-arr[i]] ){
				dp[j] = 1;
				maxi = max( maxi,j );
			}
	}
	if( maxi==q ){
		cout << maxi << endl;
		return 0;
	}
	if( tree>=q ){
		cout << maxi+(q-maxi-1) << endl;
		return 0;
	}
	q -= maxi;
	int res=maxi;
	FP( i,1,m )
		cin >> arr[i];
	sort( arr+1,arr+m+1 );
	FM( i,m,1 ){
		if( arr[i]<=q ){
			q -= arr[i];
			res += arr[i]-1;
			continue;
		}
		res += q-1;
		break;
	}
	cout << res << endl;
}

Submission Info

Judge Result