QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#698484 | #6525. New Houses | 0x3fffffff | AC ✓ | 101ms | 6548kb | C++23 | 1.2kb | 2024-11-01 19:52:05 | 2024-11-01 19:52:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m;cin >> n >> m;
vector<int>a(n + 1), b(n + 1);
priority_queue<int>q;
int sum = 0;
int ans = 0;
for (int i = 1;i <= n;i++) {
cin >> a[i] >> b[i];
sum += b[i];
q.push(a[i] - b[i]);
}
int x = m - n;
if (n == 1) {
cout << b[1] << "\n";return;
}
if (n == 2 and x >= 1) {
cout << max(a[1] + a[2], b[1] + b[2]) << "\n";return;
}
//x空位
if (2 * n - 1 <= m)
ans = max(ans, sum);
// cout << ans << "ans\n";
int cnt = 0;
sum += q.top(); q.pop();
while (q.size()) {
int u = q.top();q.pop();
cnt++;
sum += u;
// cout << sum << "\n";
if (2 * n - 1 - cnt <= m) {
// cout << cnt << "\n";
// cout << "ok\n";
ans = max(ans, sum);
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
#ifdef LOCAL
freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
#endif
cin >> T;
while (T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
3 4 5 1 100 100 1 100 1 100 1 2 2 1 10 1 10 2 3 100 50 1 1000
output:
400 2 1050
result:
ok 3 number(s): "400 2 1050"
Test #2:
score: 0
Accepted
time: 101ms
memory: 3656kb
input:
100000 6 11 191141536 365120521 799679686 648574232 102602909 467685128 405440859 796808887 384858152 191995380 433392826 195648471 5 13 831367906 510447872 795639287 575551283 811207605 176441088 240156289 946977042 133416463 721098873 5 5 806744021 699586200 630510306 637827160 49223781 641709297 ...
output:
3247545200 4106290713 2653993029 5122532137 5570513606 2031887824 2044500908 1857678917 6815058419 2237593918 6646615756 5638337819 3690874076 5497726904 5513905900 5404435094 4705403467 2411992217 3430587752 5098767681 3921151709 1445672728 2692878616 3833748807 2716183054 974485573 6464787173 8839...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 97ms
memory: 3644kb
input:
100000 2 4 171910845 724506309 259963066 888690008 7 8 953968751 356200645 849910110 806488159 854691378 564448772 233557983 165114038 255658257 12385446 666173054 713885466 955831392 860299505 2 6 813205501 321494719 279407788 802865765 4 8 57425442 736850668 801303313 183904228 13820953 38797054 4...
output:
1613196317 4817503337 1124360484 2136575299 1409199188 3637650680 6262687872 988232227 3651377959 3865729450 967276858 5411226361 5602586585 4319610954 2833710199 4042904612 532626145 3528068938 2661203300 5355268131 284146202 5233667938 6490342667 2369703443 5973463590 5902979500 6331061629 4321393...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 62ms
memory: 3884kb
input:
100000 1 1 7 4 6 16 7 5 8 2 5 6 8 5 10 4 9 3 10 25 5 10 4 5 8 10 5 10 2 6 5 9 6 8 9 10 8 6 6 7 9 13 6 7 9 8 8 1 6 5 2 10 7 1 2 2 6 4 10 3 10 28 4 3 5 3 2 3 9 10 4 2 5 8 10 8 9 1 6 5 6 6 10 27 10 4 3 6 6 4 5 9 1 5 9 9 1 10 9 2 2 6 7 4 9 27 8 8 4 5 1 1 4 2 6 4 3 9 2 8 7 8 4 4 5 11 9 8 6 4 9 4 9 2 4 3 ...
output:
4 48 82 65 65 77 53 37 28 67 59 37 37 59 14 64 7 18 69 38 42 38 49 31 54 40 37 6 6 64 34 10 49 44 14 32 4 50 35 43 43 61 56 79 6 66 68 32 15 48 59 10 41 64 52 14 48 14 47 33 62 52 9 14 41 67 10 37 26 6 46 19 34 24 63 25 49 37 66 44 2 11 34 29 23 13 26 46 41 26 24 18 2 11 55 38 3 31 4 24 25 63 47 3 7...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 75ms
memory: 6548kb
input:
10 92180 261153 4 1 6 4 1 1 2 4 6 1 3 3 6 3 1 8 7 4 7 4 4 5 8 6 3 4 6 2 8 10 4 2 6 1 5 4 10 3 6 4 8 1 10 4 3 6 9 3 10 7 10 3 3 8 1 6 10 9 4 1 7 9 3 9 9 5 6 8 7 4 1 2 6 8 10 8 4 5 6 8 2 6 8 10 2 1 5 4 9 5 8 5 4 7 5 8 6 2 5 3 4 4 9 7 9 2 4 5 10 7 2 10 5 3 4 10 3 2 9 7 3 9 7 6 10 6 8 4 7 5 3 10 2 2 2 2...
output:
658292 447048 594322 412878 350012 390453 659220 539463 407734 389596
result:
ok 10 numbers