QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #281740 | #3025. Assimilation | Dualqwq# | AC ✓ | 204ms | 14600kb | C++20 | 973b | 2023-12-10 17:15:12 | 2023-12-10 17:15:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
long long k,a[N],sa;
multiset<long long> S1,S2;
inline void work() {
cin >> n >> k;sa = 0;
for(int i = 1;i <= n;i++) cin >> a[i],sa += a[i];
S1.clear(),S2.clear();
int ans = 0;
for(int i = 1;i <= n;i++) S1.insert(a[i]);
while(k < sa) {
auto it = S1.upper_bound(k);
if(it == S1.begin()) break;
--it;
k += *it;sa -= *it;S1.erase(it);
++ans;
}
// while(S1.size()) {
// if(k >= *S1.begin()) {
// auto it = S1.upper_bound(k);
// --it;
// // printf("zhan:%d\n",*it);
// k -= *it;S2.insert(*it);S1.erase(it);
// } else if(S2.size()) {
// k += 2 * (*S2.rbegin());
// S2.erase(prev(S2.end()));
// ++ans;
// } else break;
// }
// if(S1.size()) cout << -1 << endl;
// else cout << ans << endl;
if(k < sa) cout << -1 << endl;
else cout << ans << endl;
}
int main() {
int T;
cin >> T;
while(T--) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 160ms
memory: 14568kb
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: 204ms
memory: 14600kb
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: 174ms
memory: 12824kb
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