QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731399#9540. Double 11vme50WA 36ms8176kbC++171.6kb2024-11-10 03:15:302024-11-10 03:15:32

Judging History

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

  • [2024-11-10 03:15:32]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:8176kb
  • [2024-11-10 03:15:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define db __float128
#define pii pair<int,int>
#define pli pair<ll,int>
#define vi vector<int>
#define eb emplace_back
#define po pop_back
#define par __builtin_parity
#define pct __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define gcd __gcd
#define fi first
#define se second
const int N=2e5+5;
const db alpha=(sqrt(5)-1)/2;
int n,m,a[N];ll s[N];db l,r,ml,mr,wl,wr,ans,dp[N];
int tp;pii st[N];
db f(int x,int y)
{return dp[x]+sqrtl((s[y]-s[x])*(y-x));}
int get(int x,int y,int l,int r)
{
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(f(x,mid)<=f(y,mid)) r=mid-1;
		else l=mid+1;
	}
	return r;
}
db slv(db x)
{
	tp=0;st[++tp]={0,n};
	for(int i=1,t=1;i<=n;++i)
	{
		while(t<=tp && i>st[t].se) ++t;
		st[t-1].se=i-1;
		dp[i]=f(st[t].fi,i)+x;
		while(tp>=t && f(i,st[tp-1].se+1)<=f(st[tp].fi,st[tp-1].se+1)) --tp;
		if(tp>=t) st[tp].se=get(i,st[tp].fi,st[tp-1].se+1,st[tp].se);
		if(tp<t || st[tp].se<n) st[++tp]={i,n};
	}
	return dp[n]-x*m;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
	l=0;r=1e8;
	ml=l*alpha+r*(1-alpha);mr=l*(1-alpha)+r*alpha;
	wl=slv(ml);wr=slv(mr);
	for(int _=0;_<60;++_)
	{
		ans=max({ans,wl,wr});
		if(wl<wr) l=ml,ml=mr,wl=wr,mr=l*(1-alpha)+r*alpha,wr=slv(mr);
		else r=mr,mr=ml,wr=wl,ml=l*alpha+r*(1-alpha),wl=slv(ml);
	}
	printf("%.15lf\n",(double)ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 8176kb

input:

4 2
1 2 3 4

output:

6.191147129557120

result:

ok found '6.191147130', expected '6.191147130', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 8116kb

input:

10 3
1 2 3 4 5 6 7 8 9 10

output:

22.591625366514130

result:

ok found '22.591625367', expected '22.591625367', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 5916kb

input:

1 1
1

output:

1.000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 7984kb

input:

1 1
100000

output:

316.227766016837961

result:

ok found '316.227766017', expected '316.227766017', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 5944kb

input:

7 1
10 47 53 9 83 33 15

output:

41.833001326703780

result:

ok found '41.833001327', expected '41.833001327', error '0.000000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

8 5
138 1702 119 1931 418 1170 840 1794

output:

233.901654551943579

result:

ok found '233.901654552', expected '233.901654552', error '0.000000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3876kb

input:

58 1
888 251 792 847 685 3 182 461 102 348 555 956 771 901 712 878 580 631 342 333 285 899 525 725 537 718 929 653 84 788 104 355 624 803 253 853 201 995 536 184 65 205 540 652 549 777 248 405 677 950 431 580 600 846 328 429 134 983

output:

1355.265287683559109

result:

ok found '1355.265287684', expected '1355.265287684', error '0.000000000'

Test #8:

score: 0
Accepted
time: 3ms
memory: 5940kb

input:

88 30
67117 31903 93080 85196 16438 97116 11907 72959 83651 41273 52873 81892 81468 51323 99992 58869 54258 7183 87358 90990 80596 41252 90769 82705 61434 8524 13575 10787 53950 96768 12062 34637 27806 70937 69653 28380 90236 3352 27537 3873 91006 89790 25369 91825 82734 5588 4539 74118 47098 84741 ...

output:

18791.475354094098293

result:

ok found '18791.475354094', expected '18791.475354094', error '0.000000000'

Test #9:

score: 0
Accepted
time: 36ms
memory: 8048kb

input:

987 59
5209 1618 7129 7700 893 6647 8231 3314 9844 1347 6789 2711 3968 7416 5864 9190 9564 8874 7357 2087 530 8754 7935 6772 3475 8206 2898 2717 9252 8686 6604 5188 7451 9977 9366 7618 6294 6454 3919 3232 8164 8403 8617 2191 5257 626 8554 1952 1727 4759 205 9453 3312 9387 4798 7774 7005 8892 3570 50...

output:

66075.508587054646341

result:

ok found '66075.508587055', expected '66075.508587055', error '0.000000000'

Test #10:

score: -100
Wrong Answer
time: 21ms
memory: 7944kb

input:

572 529
48392 84311 16267 29255 52276 20511 75195 95522 64489 52229 74478 69766 41777 25148 59976 66512 62953 16779 69312 98832 96131 94700 46403 58028 12868 83503 80367 51036 63398 7509 55193 76715 29143 75925 89863 89244 5561 21242 9047 89763 78016 86274 11382 88520 72343 29729 70986 86600 43707 7...

output:

119849.321969332231674

result:

wrong answer 1st numbers differ - expected: '119849.3226818', found: '119849.3219693', error = '0.0000000'