UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202785#3549. heapJosephcheng100460ms2764kbC++11579b2024-02-17 09:27:302024-02-17 13:14:20

answer

#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;

LL n,k,l,r,mid;
LL a[N],b[N];

bool check(LL x)
{
	LL cnt=0,R=n;
	for(int L=1;L<=n;L++){
		for(;1ll*a[L]*b[R]>x;R--) ;
		cnt+=R;
	}
	return cnt<k;
}

int main()
{
	a[0]=b[0]=-0x3f3f3f3f;
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	l=a[1]*b[1],r=a[n]*b[n];
	while(l<=r){
		mid=l+r>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	printf("%lld",l);
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 1220kb

input:

1000 418719
5147623 136053348 213617322 723259083 883264334 186077831 465758109 960894669 728226984 ...

output:

169088650018633829

result:

ok single line: '169088650018633829'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1220kb

input:

1000 639203
771477784 582104359 879708649 827429779 565088349 869887075 379154764 1005385809 7088438...

output:

306629262243319168

result:

ok single line: '306629262243319168'

Test #3:

score: 10
Accepted
time: 57ms
memory: 2764kb

input:

100000 49321
880411191 36041260 965827491 523298325 680702878 22269411 403551965 929342754 802680687...

output:

612728495258

result:

ok single line: '612728495258'

Test #4:

score: 10
Accepted
time: 50ms
memory: 2764kb

input:

100000 52525
589049616 338238682 899962142 642967974 803950053 346365970 971085766 477343418 1069939...

output:

559705121598

result:

ok single line: '559705121598'

Test #5:

score: 10
Accepted
time: 39ms
memory: 2764kb

input:

100000 36857
943771339 451663012 397385981 143741539 1002615714 85392790 462922778 676655035 8741483...

output:

338700884472

result:

ok single line: '338700884472'

Test #6:

score: 10
Accepted
time: 40ms
memory: 2760kb

input:

100000 38777
1024597744 191067205 853092569 482793386 407756833 855084304 645861493 157082277 101202...

output:

527978939345

result:

ok single line: '527978939345'

Test #7:

score: 10
Accepted
time: 64ms
memory: 2760kb

input:

100000 3810838482
372635897 36130305 417593352 973040030 93463182 258506556 606679088 877855426 9303...

output:

141575056752855110

result:

ok single line: '141575056752855110'

Test #8:

score: 10
Accepted
time: 72ms
memory: 2760kb

input:

100000 5037415885
450616223 293394278 483391400 317841116 426941474 619345970 366274237 549758912 10...

output:

217104583799680752

result:

ok single line: '217104583799680752'

Test #9:

score: 10
Accepted
time: 68ms
memory: 2764kb

input:

100000 5935997422
557273539 821711748 556723556 1065870715 309362659 131921994 589731152 642223017 8...

output:

285231138030161376

result:

ok single line: '285231138030161376'

Test #10:

score: 10
Accepted
time: 69ms
memory: 2764kb

input:

100000 3833786143
6063607 824949917 38140330 202365 53693680 855246517 100369614 24151957 156345386 ...

output:

143497852602005880

result:

ok single line: '143497852602005880'