QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560612#8815. Space Stationucup-team3651WA 0ms3828kbC++142.2kb2024-09-12 16:57:272024-09-12 16:57:28

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 16:57:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-09-12 16:57:27]
  • 提交

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'