QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710740#9540. Double 11ucup-team5217#WA 1ms3976kbC++232.5kb2024-11-04 21:19:232024-11-04 21:19:23

Judging History

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

  • [2024-11-04 21:19:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3976kb
  • [2024-11-04 21:19:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define double long double
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    vector<ll> prea(n+1);
    for(int i=1;i<=n;i++)   cin>>a[i];
    sort(a.begin()+1,a.end());
    for(int i=1;i<=n;i++)   prea[i]=prea[i-1]+a[i];
    auto DP_2_deque=[&](double dj,int t)->pair<int,double> {
        vector<pair<int,double>> dp(n+1);
        struct node{int x,l,r;};
        deque<node> qe;
        auto get_w=[&](int l,int r)->double {
            return sqrt(1ll*(r-l)*(prea[r]-prea[l]))-dj;
        };
        auto get_l_r=[&](int l,int r)->pair<int,double> {
            return {dp[l].first+1,dp[l].second+get_w(l,r)};
        };
        auto cmp=[&](pair<int,double> x,pair<int,double> y)->bool {
            if(t==-1)   {
                if(x.second!=y.second)  return x.second<y.second;
                else return x.first<y.first;
            }
            else{
                if(x.second!=y.second)  return x.second>y.second;
                else return x.first<y.first;
            }
        };
        qe.push_back({0,1,n});
        for(int i=1;i<=n;i++){
            while(!qe.empty()&&qe.front().r<i)  qe.pop_front();
            dp[i]=get_l_r(qe.front().x,i);
            qe.begin()->l=i+1;
            while(!qe.empty()){
                int it=qe.back().l;
                if(!cmp(get_l_r(qe.back().x,it),get_l_r(i,it))) qe.pop_back();
                else break;
            }
            if(qe.empty())  qe.push_back({i,i+1,n});
            else{
                auto [x,l,r]=qe.back();
                int le=l,re=r;
                while(le<re){
                    int mid=(le+re+1)>>1;
                    if(cmp(get_l_r(x,mid),get_l_r(i,mid)))  le=mid;
                    else re=mid-1;
                }
                qe.rbegin()->r=le;
                if(le+1<=n) qe.push_back({i,le+1,n});
            }
        }
        return dp[n];
    };
    double maxn=0;
    for(int i=1;i<=n;i++)   maxn+=n*1.0/a[i];
    double le=0,re=maxn;
    const double eps=1e-15;
    while(re>le+eps){
        double mid=(le+re)/2;
        pair<int,double> res=DP_2_deque(-mid,-1);
        if(res.first<=m)    re=mid;
        else le=mid;
    }
    pair<int,double> res=DP_2_deque(-le,-1);
    cout<<setprecision(14)<<res.second-m*le<<'\n';
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int _ =1;
    while(_--)  solve();
    return 0;
}

详细

Test #1:

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

input:

4 2
1 2 3 4

output:

6.1911471295571

result:

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

Test #2:

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

input:

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

output:

22.591625366514

result:

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

Test #3:

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

input:

1 1
1

output:

1

result:

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

Test #4:

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

input:

1 1
100000

output:

316.22776601684

result:

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

Test #5:

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

input:

7 1
10 47 53 9 83 33 15

output:

41.833001326704

result:

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

Test #6:

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

input:

8 5
138 1702 119 1931 418 1170 840 1794

output:

233.90165455194

result:

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

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3936kb

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:

1343.3845761453

result:

wrong answer 1st numbers differ - expected: '1355.2652877', found: '1343.3845761', error = '0.0087663'