QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#236221 | #3025. Assimilation | ahsoltan# | AC ✓ | 137ms | 12992kb | C++20 | 1.4kb | 2023-11-03 18:32:00 | 2023-11-03 18:32:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
#define ir(x,a,b) ((a) <= (x) && (x) <= (b))
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define foru(i, n) for (int i = 0; i < n; ++i)
#define fori(i,a,n) for (int i = a; i < n; ++i)
// #ifdef LOCAL
// auto& operator<<(auto&, pair<auto, auto>);
// template<typename T, typename = T::value_type>
// auto& operator<<(auto& o, T x) requires (!same_as<T, string>) {
// o << "{";
// string s;
// for (auto i : x) {
// o << s << i;
// s << ", ";
// }
// return o << "}";
// }
// auto& operator<<(auto& o, pair<auto, auto> p) {
// return o << "(" << p.first << ", " << p.second << ")";
// }
// #define debug(x..) cerr << "["#x"]:",[](auto...$){((cerr<<" "<<$),...)<<endl;}(x)
// #else
// #define debug(...) 2137
// #endif
void solve() {
multiset<ll> S;
ll n, k;
cin >> n >> k;
ll sum = 0;
foru (i, n) {
ll x;
cin >> x;
sum += x;
S.insert(x);
}
int ct = 0;
//cout << sum << " " << k << endl;
while (k < sum) {
auto it = S.upper_bound(k);
if (it == S.begin()) {
cout << "-1\n";
return;
}
--it;
++ct;
k += (*it);
sum -= (*it);
//cout << "taking " << *it << endl;
//cout << sum << " " << k << endl;
S.erase(it);
}
cout << ct << "\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int z;
cin >> z;
while (z--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 110ms
memory: 12972kb
input:
29 9 1 1 1 2 1 1 1 1 1 1 4 1 3 2 1 1 5 316660370 269357435 105688553 346785866 295093544 181703417 6 43402885 39947441 27068237 43810814 44913378 40095941 34779892 22 319594 3815194 3056481 6593888 7315914 6593888 4794774 2561877 5256242 4920603 5256242 3606645 864746 1594265 1235578 2361430 2277526...
output:
4 2 2 3 -1 10621 4 -1 7 5385 8 2 -1 5 6264 3 0 -1 124764 5 -1 7 10940 1 3 100000 5 -1 -1
result:
ok 29 lines
Test #2:
score: 0
Accepted
time: 137ms
memory: 12992kb
input:
30 1537 2 5 6 3 3 6 5 3 5 5 5 6 5 5 6 4 6 6 6 4 3 5 5 5 6 4 6 2 3 4 5 5 5 5 5 6 6 6 4 4 4 2 6 6 5 3 6 5 6 6 5 6 5 4 3 5 6 4 3 5 3 6 4 5 6 4 1 4 6 4 5 2 4 3 4 6 6 5 5 5 6 6 5 5 5 6 4 5 6 6 6 5 5 5 3 3 2 4 6 3 5 4 4 6 6 6 5 5 6 4 4 6 6 6 6 4 6 6 3 4 5 5 3 4 5 4 6 5 5 6 5 6 6 3 3 6 5 4 6 4 6 6 4 5 3 2 ...
output:
629 22 1452 10 2121 5094 6 1135 7123 2140 4 916 1802 1237 5 6 1498 262 115823 1223 11 1032 844 13 1899 4 1212 17 -1 1797
result:
ok 30 lines
Test #3:
score: 0
Accepted
time: 125ms
memory: 11628kb
input:
30 11 40454552 9677001 192936684 252254034 192936684 37357273 9156546 74500194 116624778 13650360 2174119 13650360 27 1 3 2 3 1 3 5 3 5 1 1 1 1 1 1 4 4 1 1 1 2 1 3 3 1 3 2 4 11 72578887 172937772 206562668 87600829 84557056 103901588 148396091 92438037 215698807 125600579 216304481 191851963 5 1 1 2...
output:
4 9 -1 3 19 -1 5 9 4 4 18 14 5 5 83242 7 4 -1 6 22 5 3 17 -1 2 7 22 158159 -1 12
result:
ok 30 lines