QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710740 | #9540. Double 11 | ucup-team5217# | WA | 1ms | 3976kb | C++23 | 2.5kb | 2024-11-04 21:19:23 | 2024-11-04 21:19:23 |
Judging History
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'