Advertisement
erek1e

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. }
Advertisement
RAW Paste Data Copied
Advertisement