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