QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699986#9540. Double 11ucup-team4863#WA 0ms3932kbC++141.7kb2024-11-02 11:29:002024-11-02 11:29:02

Judging History

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

  • [2024-11-02 11:29:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3932kb
  • [2024-11-02 11:29:00]
  • 提交

answer

// created:  2024-11-02 11:08:20
#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int N=2e5+5;
int n,m,a[N];
double s[N];
double cost(int l,int r){return sqrt((r-l)*(s[r]-s[l]));}
pair<double,int> f[N];
pair<int,int> q[N];
int qf,qr;
double pre(int l,int r){return f[l].first+cost(l,r);}
void dp(double pe)
{
	f[0]={0,0};qf=0;qr=0;q[qr++]={0,0};
	F(i,1,n+1)
	{
		++q[qf].second;
		if(qf+1<qr&&q[qf].second==q[qf+1].second)++qf;
		f[i]=f[q[qf].first];
		f[i].first+=pe+cost(q[qf].first,i);f[i].second+=1;
		while(qf<qr&&pre(q[qr-1].first,q[qr-1].second)>pre(i,q[qr-1].second))--qr;
		if(qf<qr)
		{
			int l=q[qr-1].second,r=n+1;
			while(r-l>1)
			{
				int mid=(l+r)>>1;
				if(pre(q[qr-1].first,mid)>pre(i,mid))r=mid;
				else l=mid;
			}
			if(r<=n)q[qr++]={i,r};
		}
		else q[qr++]={i,i};
	}
}
int main()
{
	read(n,m);
	F(i,0,n)read(a[i]);
	sort(a,a+n);
	F(i,0,n)s[i+1]=s[i]+a[i];
	double l=0,r=1e18;
	while(r-l>1e-13*max(l,1.0))
	{
		double mid=l+(r-l)/2.0;
		dp(mid);
		if(f[n].second<m)r=mid;
		else l=mid;
	}
	double mid=l+(r-l)/2.0;
	dp(mid);
	printf("%.11lf\n",f[n].first-m*mid);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1904kb

input:

4 2
1 2 3 4

output:

6.19114712956

result:

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

Test #2:

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

input:

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

output:

22.59162536651

result:

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

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 2048kb

input:

1 1
1

output:

0.00000000000

result:

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