QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722860#9540. Double 11eastcloudWA 0ms7848kbC++172.5kb2024-11-07 20:26:292024-11-07 20:26:30

Judging History

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

  • [2024-11-07 20:26:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7848kb
  • [2024-11-07 20:26:29]
  • 提交

answer


#include<bits/stdc++.h>

#define ll long long
#define pi pair<ll,ll>
#define vi vector<ll>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array

using namespace std;

#define N 500005

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

ll n,m;
ll a[N],s[N];
struct tup{
    ll x,l,r;
    tup(ll x=0,ll l=0,ll r=0):x(x),l(l),r(r){}
};

deque<tup> q;
long double f[N];
ll g[N];

long double w(ll pos,ll r){
    return sqrtl((r-pos)*(s[r]-s[pos]));
}
long double calc(long double k){
    while(q.size())q.pop_front();
    q.push_front(tup(0,1,n));
    for(ll i=1;i<=n;i++){
        ll pos=q.front().x;
        f[i]=f[pos]+w(pos,i)+k;g[i]=g[pos]+1;
        if(q.front().l==q.front().r)q.pop_front();
        else{
            auto [x,l,r]=q.front();q.pop_front();
            q.push_front(tup(x,l+1,r));
        }
        while(q.size() && f[i]+w(i,q.back().l)<=f[q.back().x]+w(q.back().x,q.back().l))q.pop_back();
        if(q.size()){
            if(f[i]+w(i,q.back().r)<=f[q.back().x]+w(q.back().x,q.back().r)){
                pos=q.back().x;ll l=q.back().l,r=q.back().r;
                while(l<r){
                    ll mid=(l+r)>>1;
                    if(f[i]+w(i,mid)<=f[pos]+w(pos,mid))r=mid;
                    else l=mid+1;
                }
                auto [X,L,R]=q.back();q.pop_back();
                q.push_back(tup(X,L,l-1));
            }
        }
        
        if(q.size() && q.back().r!=n)q.push_back(tup(i,q.back().r+1,n));
        if(!q.size())q.push_back(tup(i,i+1,n));
    }
    return f[n];
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif

    n=read(),m=read();
    for(ll i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);
    for(ll i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    long double L=-0x3f3f3f3f3f3f,R=0x3f3f3f3f3f3f,eps=1e-9;
    while(R-L>eps){
        long double mid=(L+R)/2;calc(mid);
        if(calc(mid)-mid*m<=calc(mid+eps)-(mid+eps)*m)L=mid;
        else R=mid;
    }
    printf("%.12Lf",calc(L)-L*m);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 2
1 2 3 4

output:

-69540876599096.675445556641

result:

wrong answer 1st numbers differ - expected: '6.1911471', found: '-69540876599096.6718750', error = '11232308834514.4277344'