QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #699997 | #9540. Double 11 | ucup-team3555# | WA | 71ms | 791908kb | C++20 | 608b | 2024-11-02 11:31:23 | 2024-11-02 11:31:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=2e5+3,M=503;
const db INF=1e18;
ll n,m,a[N];
db sa[N],f[N][M];
void Min(db &x,db y){if(x>y)x=y;}
int main()
{
cin>>n>>m;
assert(m<M);
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)sa[i]=sa[i-1]+a[i];
for(int i=0;i<N;i++)for(int j=0;j<M;j++)f[i][j]=INF;
f[0][0]=0;
for(ll i=0;i<=n;i++)for(int j=0;j<=min(m,i);j++)
{
for(int k=i+1;k<=n&&(k-i)*(m-j)<=n;k++)Min(f[k][j+1],f[i][j]+sqrtl((sa[k]-sa[i])*(k-i)));
}
cout<<fixed<<setprecision(12)<<f[n][m];
}
詳細信息
Test #1:
score: 100
Accepted
time: 71ms
memory: 791656kb
input:
4 2 1 2 3 4
output:
6.191147129557
result:
ok found '6.191147130', expected '6.191147130', error '0.000000000'
Test #2:
score: 0
Accepted
time: 59ms
memory: 791812kb
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: 52ms
memory: 791908kb
input:
1 1 1
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 51ms
memory: 791908kb
input:
1 1 100000
output:
316.227766016838
result:
ok found '316.227766017', expected '316.227766017', error '0.000000000'
Test #5:
score: 0
Accepted
time: 43ms
memory: 789808kb
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: -100
Wrong Answer
time: 52ms
memory: 791572kb
input:
8 5 138 1702 119 1931 418 1170 840 1794
output:
234.101592384777
result:
wrong answer 1st numbers differ - expected: '233.9016546', found: '234.1015924', error = '0.0008548'