QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#141191 | #6525. New Houses | cy1999 | WA | 203ms | 3884kb | C++20 | 942b | 2023-08-17 09:20:23 | 2023-08-17 09:20:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m,r1,r2,res;
struct node{
int a,b;
friend bool operator<(node a,node b){
return a.a-a.b>b.a-b.b;
}
}p[500005];
int solve(){
int l=0,r=n;
while(l<r){
int mid=l+r>>1;
if(mid+2*(n-mid)<=m)r=mid;
else l=mid+1;
}
if(2*n-1<=m)return 0;
return l;
}
signed main(){
cin>>t;
while(t--){
cin>>n>>m;r1=r2=0;res=0;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&p[i].a,&p[i].b);
if(p[i].a>p[i].b)r1++;
else r2++;
}
sort(p+1,p+n+1);
int k=solve();
if(r1==1&&k<=1){
for(int i=1;i<=n;i++)res+=p[i].b;
printf("%lld\n",res);
continue;
}
if(r1>=k){
for(int i=1;i<=n;i++)res+=max(p[i].a,p[i].b);
printf("%lld\n",res);
continue;
}
for(int i=1;i<=k;i++)res+=p[i].a;
for(int i=k+1;i<=n;i++)res+=p[i].b;
printf("%lld\n",res);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
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: -100
Wrong Answer
time: 203ms
memory: 3884kb
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 1345295010 6815058419 2237593918 6646615756 5638337819 3690874076 5497726904 5513905900 5404435094 4705403467 2411992217 3430587752 5098767681 3921151709 1271949960 2692878616 3833748807 2409784919 974485573 6464787173 8839...
result:
wrong answer 8th numbers differ - expected: '1857678917', found: '1345295010'