QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #699991 | #9540. Double 11 | ucup-team3555# | WA | 64ms | 791976kb | C++20 | 607b | 2024-11-02 11:30:29 | 2024-11-02 11:30:31 |
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],sa[N];
db 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]+sqrt((sa[k]-sa[i])*(k-i)));
}
cout<<fixed<<setprecision(12)<<f[n][m];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 52ms
memory: 791808kb
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: 39ms
memory: 791932kb
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: 24ms
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: 791976kb
input:
1 1 100000
output:
316.227766016838
result:
ok found '316.227766017', expected '316.227766017', error '0.000000000'
Test #5:
score: 0
Accepted
time: 31ms
memory: 791964kb
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: 64ms
memory: 789928kb
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'