QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560612 | #8815. Space Station | ucup-team3651 | WA | 0ms | 3828kb | C++14 | 2.2kb | 2024-09-12 16:57:27 | 2024-09-12 16:57:28 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define N 101
#define mod 998244353
#define inf 1e9
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(int x){
if(x<0)x=-x,putchar('-');
if(x/10)write(x/10);
putchar(x%10+'0');
}
int qp(int x,int y=mod-2){int ans=1;while(y){if(y&1)ans=ans*1ll*x%mod;x=x*1ll*x%mod;y>>=1;}return ans;}
struct frac{
double val;
int res;
frac(double val=0,int res=0):val(val),res(res){}
frac operator +(const frac &x)const{
return frac(val+x.val,(res+x.res)%mod);
}
frac operator +(const int &x)const{
return frac(val+x,(res+x)%mod);
}
frac operator *(const frac &x)const{
return frac(val*x.val,(res*1ll*x.res)%mod);
}
}f[N][N];
int a[N];
int main(){
#ifdef EAST_CLOUD
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int n=read(),m=read(),cnt=0,sum=0,sum2=0;
for(int i=1;i<=n;i++)a[i]=read(),cnt+=(a[i]>m),sum+=(a[i]>m?a[i]:0),sum2+=(a[i]<=m?a[i]:0);
if(cnt==n){write(n*m);return 0;}
if(cnt==0){write(sum2);return 0;}
frac E=frac(sum*1.0/cnt,sum*1ll*qp(cnt)%mod),E2=frac(sum2*1.0/(n-cnt),sum2*1ll*qp(n-cnt)%mod);
for(int j=0;j<=n;j++)f[n+1][j]=frac(inf,0);
f[n+1][cnt]=frac(0,0);
for(int i=n;i>=1;i--){
for(int j=min(i,cnt);j>=max(0,cnt-(n-i+1));j--){
int A=n-i+1,B=cnt-j;
frac p=frac(B*1.0/A,B*1ll*qp(A)%mod);
frac q=frac((A-B)*1.0/A,(A-B)*1ll*qp(A)%mod);
f[i][j]=frac(m,m)+p*f[i+1][j+1]+q*f[i+1][j];
frac tmp;
tmp=E*p+p*f[i+1][j+1]+q*E2+q*f[i+1][j];
if(tmp.val<f[i][j].val)f[i][j]=tmp;
}
}
write(f[1][0].res);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
3 3 2 3 4
output:
499122185
result:
ok 1 number(s): "499122185"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 1 10 20 30 40 50
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
1 9 37
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
5 5 24 41 29 6 40
output:
25
result:
ok 1 number(s): "25"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3740kb
input:
10 34 91 86 1 14 98 13 85 64 91 20
output:
569633414
result:
wrong answer 1st numbers differ - expected: '707882334', found: '569633414'