QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#141191#6525. New Housescy1999WA 203ms3884kbC++20942b2023-08-17 09:20:232023-08-17 09:20:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-17 09:20:25]
  • 评测
  • 测评结果:WA
  • 用时:203ms
  • 内存:3884kb
  • [2023-08-17 09:20:23]
  • 提交

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'