 # IOI '04 P5 - Farmer

Jul 3rd, 2022
1,172
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <bitset>
4. #include <algorithm>
5. #include <numeric>
6.
7. using namespace std;
8.
9. const int Q = 150000;
10.
11. int main() {
12.     int q, m, k;
13.     cin >> q >> m >> k;
14.     vector<int> a(m), b(k);
15.     for (int &x : a) cin >> x;
16.     for (int &x : b) cin >> x;
17.
18.     // use up as many nodes as possible on complete cycles (e.g. take all cycles if you can)
19.     bitset<Q+1> can = 1; // knapsack
20.     for (int x : a) can |= can << x;
21.     int useOnCycles = q;
22.     while (!can[useOnCycles]) --useOnCycles;
23.     q -= useOnCycles;
24.     //  but we also want to find largest one that can be left unused
25.     //  so find largest that can be used to build (totalCycles - useOnCycles), and then use all the others
26.     int targetSum = accumulate(a.begin(), a.end(), 0) - useOnCycles;
27.     sort(a.begin(), a.end());
28.     vector<int> big(1+targetSum); // same knapsack, but instead of true or false, store largest one that can be used
29.     for (int i = 1; i <= m; ++i) {
30.         for (int j = targetSum-a[i-1]; j >= 0; --j) {
31.             if (j && !big[j]) continue;
32.             big[j+a[i-1]] = i;
33.         }
34.     }
35.     /*  find the biggest and add it to the lines
36.         (definitely do not need to add more than one to lines -
37.          we have tried to fill up as many cycles as possible so we don't have
38.          enough left over to full up even the smallest remaining cycle)
39.     */
40.     b.push_back(a[big[targetSum]-1]);
41.
42.     // use the rest on segments but using as few segments as possible
43.     int edges = useOnCycles;
44.     sort(b.rbegin(), b.rend());
45.     for (int i = 0; i < k && q; ++i) {
46.         int spend = min(q, b[i]);
47.         edges += spend-1;
48.         q -= spend;
49.     }
50.
51.     cout << edges << endl;
52.     return 0;
53. }