Submission #330298

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

int n,m,k,i,a[2004],b[2004];
int j,dp[150004];
int ans,h[2005];

vector<int> v;

int main(){
    cin >> n >> m >> k;

    for(i=1 ; i<=m ; i++){
        cin >> a[i];
    }

    for(i=1 ; i<=k ; i++){
        cin >> b[i];
    }

    sort(a+1,a+m+1);

    dp[0] = -1;

    for(i=1 ; i<=m ; i++){
        for(j=n ; j>=0 ; j--){
            if(dp[j] and !dp[j+a[i]]){
                dp[j+a[i]] = i;
            }
        }
    }

    for(i=n ; i>=0 ; i--){
        if(dp[i])
            break;
    }

    int x = i;

    ans = x;

    n -= x;

    while(dp[x] != -1){
        h[dp[x]] = 1;
        x -= a[dp[x]];
    }

    for(i=1 ; i<=m ; i++)
        if(!h[i])
            v.pb(a[i]);

    for(i=1 ; i<=k ; i++){
        v.pb(b[i]);
    }

    sort(v.begin(),v.end());

    for(i=v.size()-1 ; i>=0 ; i--){
        if(!n)
            break;
        ans += min(v[i],n)-1;
        n -= min(v[i],n);
    }

    cout << ans << endl;
}

Submission Info

Judge Result