Advertisement
achulkov2

Untitled

Oct 25th, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. #include <set>
  8. #include <deque>
  9.  
  10. using namespace std;
  11.  
  12. using item = pair<int, int>;
  13. int n, c;
  14. vector<item> items;
  15.  
  16. void read() {
  17.     cin >> n;
  18.     items.resize(n);
  19.     for (int i = 0; i < n; ++i) {
  20.         int w;
  21.         cin >> w;
  22.         items.emplace_back(w, i);
  23.     }
  24.     cin >> c;
  25. }
  26.  
  27. const int INF = 200;
  28.  
  29. void solve() {
  30.     int sm = 0;
  31.     for (int i = 0; i < n; ++i) {
  32.         sm += items[i].first;
  33.     }
  34.     sort(items.begin(), items.end());
  35.     auto ci(items);
  36.     reverse(items.begin(), items.end());
  37.     while (sm > c) {
  38.         sm -= items.back().first;
  39.         items.pop_back();
  40.     }
  41.     reverse(items.begin(), items.end());
  42.     auto it = upper_bound(ci.begin(), ci.end(), {c - sm, INF});
  43.     if (it == ci.end()) {
  44.         cout << "YES\n";
  45.         return;
  46.     }
  47.     vector<item> v;
  48.     int s = 0;
  49.     while (it != ci.end() && s + it->first <= c) {
  50.         v.push_back(*it);
  51.         s += it->first;
  52.         ++it;
  53.     }
  54.     if (items.size() < v.size()) {
  55.         cout << "NO\n3\n";
  56.         cout << v.size() << "\n";
  57.         for (int i = 0; i < v.size(); ++i) {
  58.             cout << v[i].second + 1 << " ";
  59.         }
  60.         cout << items.size() << "\n";
  61.         for (int i = 0; i < items.size(); ++i) {
  62.             cout << items[i].second + 1 << " ";
  63.         }
  64.         cout << "\n";
  65.     } else {
  66.         cout << "YES\n";
  67.     }
  68.  
  69. }
  70.  
  71.  
  72. int main() {
  73.     read();
  74.     solve();
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement