QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138430 | #6525. New Houses | meomeo# | AC ✓ | 87ms | 4940kb | C++14 | 1.3kb | 2023-08-11 18:18:20 | 2023-08-11 18:18:23 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool cmp(pair<int, int> &A, pair<int, int> &B) {
return (A.second - A.first) < (B.second - B.first);
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
// freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int k = m - n;
int s = 0, s2 = 0;
vector<pair<int, int>> a(n);
for (auto &[u, v]: a) {
cin >> u >> v;
s += u;
s2 += v;
}
if (n == 1) {
cout << a[0].second << "\n";
continue;
}
sort(a.begin(), a.end(), cmp);
int res = s;
while (k) {
if (a.size() == 2) {
s = max(s, s + a[0].second + a[1].second - a[0].first - a[1].first);
break;
}
if (a.size() == 0) break;
if (a.back().second - a.back().first <= 0) break;
s += a.back().second - a.back().first;
res = max(res, s);
a.pop_back();
k -= 1;
}
cout << s << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3464kb
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: 87ms
memory: 3480kb
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: 68ms
memory: 3472kb
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: 55ms
memory: 3536kb
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: 58ms
memory: 4940kb
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