QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710738#9540. Double 11ucup-team5217#WA 0ms3944kbC++232.4kb2024-11-04 21:18:052024-11-04 21:18:06

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
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-9;
    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(10)<<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: 3776kb

input:

4 2
1 2 3 4

output:

6.191147129

result:

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

Test #2:

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

input:

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

output:

22.59162537

result:

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

Test #3:

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

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: 3860kb

input:

1 1
100000

output:

316.227766

result:

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

Test #5:

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

input:

7 1
10 47 53 9 83 33 15

output:

41.83300133

result:

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

Test #6:

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

input:

8 5
138 1702 119 1931 418 1170 840 1794

output:

233.9016546

result:

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

Test #7:

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

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.384576

result:

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