IOI '04 P5 - Farmer

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <numeric>

using namespace std;

const int Q = 150000;

int main() {
    int q, m, k;
    cin >> q >> m >> k;
    vector<int> a(m), b(k);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    // use up as many nodes as possible on complete cycles (e.g. take all cycles if you can)
    bitset<Q+1> can = 1; // knapsack
    for (int x : a) can |= can << x;
    int useOnCycles = q;
    while (!can[useOnCycles]) --useOnCycles;
    q -= useOnCycles;
    //  but we also want to find largest one that can be left unused
    //  so find largest that can be used to build (totalCycles - useOnCycles), and then use all the others
    int targetSum = accumulate(a.begin(), a.end(), 0) - useOnCycles;
    sort(a.begin(), a.end());
    vector<int> big(1+targetSum); // same knapsack, but instead of true or false, store largest one that can be used
    for (int i = 1; i <= m; ++i) {
        for (int j = targetSum-a[i-1]; j >= 0; --j) {
            if (j && !big[j]) continue;
            big[j+a[i-1]] = i;
        }
    }
    /*  find the biggest and add it to the lines
        (definitely do not need to add more than one to lines -
         we have tried to fill up as many cycles as possible so we don't have
         enough left over to full up even the smallest remaining cycle)
    */
    b.push_back(a[big[targetSum]-1]);

    // use the rest on segments but using as few segments as possible
    int edges = useOnCycles;
    sort(b.rbegin(), b.rend());
    for (int i = 0; i < k && q; ++i) {
        int spend = min(q, b[i]);
        edges += spend-1;
        q -= spend;
    }

    cout << edges << endl;
    return 0;
}