Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <random>
- #include <ctime>
- #include <tuple>
- #include <unordered_set>
- #include <deque>
- #include <cassert>
- using namespace std;
- using i32 = int32_t;
- using i64 = int64_t;
- using ui32 = uint32_t;
- using ui64 = uint64_t;
- int main() {
- freopen("knapsack.in", "r", stdin);
- freopen("knapsack.out", "w", stdout);
- int n;
- cin >> n;
- vector <pair<int,int>> w(n);
- int wa = 0;
- for (int i = 0; i < n; ++i) {
- cin >> w[i].first;
- wa += w[i].first;
- w[i].second = i;
- }
- int c;
- cin >> c;
- sort(w.begin(), w.end());
- deque<pair<int,int>> a(w.begin(), w.end());
- while (wa > c) {
- wa -= a[0].first;
- a.pop_front();
- }
- auto it = upper_bound(w.begin(), w.end(), make_pair(c - wa,n));
- if (it == w.end()) {
- cout << "YES";
- return 0;
- }
- deque<pair<int,int>> b;
- int wb = 0;
- for (; it != w.end(); ++it) {
- //assert((it->first) > c - wa);
- if (wb + (it->first) <= c) {
- b.push_back(*it);
- wb += it->first;
- } else {
- break;
- }
- }
- if (b.size() > a.size()) {
- cout << "NO\n3\n";
- cout << b.size() << " ";
- for (auto& x : b) {
- cout << x.second + 1 << " ";
- }
- cout << "\n" << a.size() << " ";
- for (auto& x : a) {
- cout << x.second + 1 << " ";
- }
- cout << '\n';
- } else {
- cout << "YES\n";
- }
- }
Add Comment
Please, Sign In to add comment