QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731401#9540. Double 11vme50WA 0ms6032kbC++171.5kb2024-11-10 03:18:042024-11-10 03:18:05

Judging History

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

  • [2024-11-10 03:18:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:6032kb
  • [2024-11-10 03:18:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define db double
#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;_<80;++_)
	{
		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",ans);
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 6032kb

input:

4 2
1 2 3 4

output:

nan

result:

wrong output format Expected double, but "nan" found