achulkov2

Untitled

Oct 25th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <ctime>
  6. #include <tuple>
  7. #include <unordered_set>
  8. #include <deque>
  9. #include <cassert>
  10.  
  11. using namespace std;
  12.  
  13. using i32 = int32_t;
  14. using i64 = int64_t;
  15. using ui32 = uint32_t;
  16. using ui64 = uint64_t;
  17.  
  18.  
  19. int main() {
  20.     freopen("knapsack.in", "r", stdin);
  21.     freopen("knapsack.out", "w", stdout);
  22.     int n;
  23.     cin >> n;
  24.     vector <pair<int,int>> w(n);
  25.     int wa = 0;
  26.     for (int i = 0; i < n; ++i) {
  27.         cin >> w[i].first;
  28.         wa += w[i].first;
  29.         w[i].second = i;
  30.     }
  31.     int c;
  32.     cin >> c;
  33.  
  34.     sort(w.begin(), w.end());
  35.     deque<pair<int,int>> a(w.begin(), w.end());
  36.     while (wa > c) {
  37.         wa -= a[0].first;
  38.         a.pop_front();
  39.     }
  40.  
  41.     auto it = upper_bound(w.begin(), w.end(), make_pair(c - wa,n));
  42.     if (it == w.end()) {
  43.         cout << "YES";
  44.         return 0;
  45.     }
  46.  
  47.     deque<pair<int,int>> b;
  48.     int wb = 0;
  49.     for (; it != w.end(); ++it) {
  50.         //assert((it->first) > c - wa);
  51.         if (wb + (it->first) <= c) {
  52.             b.push_back(*it);
  53.             wb += it->first;
  54.         } else {
  55.             break;
  56.         }
  57.     }
  58.    
  59.     if (b.size() > a.size()) {
  60.         cout << "NO\n3\n";
  61.         cout << b.size() << " ";
  62.         for (auto& x : b) {
  63.             cout << x.second + 1 << " ";
  64.         }
  65.         cout << "\n" << a.size() << " ";
  66.         for (auto& x : a) {
  67.             cout << x.second + 1 << " ";
  68.         }
  69.         cout << '\n';
  70.     } else {
  71.         cout << "YES\n";
  72.     }
  73. }
Add Comment
Please, Sign In to add comment