Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // OK http://contest.uni-smr.ac.ru/ru/problemset/6267/
- # include <iostream>
- # include <vector>
- # include <set>
- using namespace std;
- bool check(vector<uint32_t> &m, size_t &mid, size_t &n, uint64_t &d) {
- multiset<uint64_t> q;
- bool is_good = true;
- for (size_t i = 0; i < mid; i++) {
- q.insert(m[i]);
- }
- for (size_t i = mid; i < n; i++) {
- size_t x = *q.begin();
- q.erase(q.begin());
- if (x + m[i] > d) {
- is_good = false;
- break;
- } else {
- q.insert(x + m[i]);
- }
- }
- return !is_good or *--q.end() > d;
- }
- int main() {
- size_t n;
- uint64_t d;
- cin >> n >> d;
- vector<uint32_t> m(n);
- for (size_t i = 0; i < n; i++) {
- cin >> m[i];
- }
- size_t left = 0;
- size_t right = n;
- while (right - left > 1) {
- size_t mid = (left + right) / 2;
- if (check(m, mid, n, d)) {
- left = mid;
- } else {
- right = mid;
- }
- }
- if (!check(m, right, n, d)) {
- cout << right;
- } else {
- cout << -1;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment