QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#731401 | #9540. Double 11 | vme50 | WA | 0ms | 6032kb | C++17 | 1.5kb | 2024-11-10 03:18:04 | 2024-11-10 03:18:05 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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