Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
29438 LYLAKIOI 【BJ】T1 C++ 运行超时 80 1000 MS 340 KB 1623 2024-05-08 13:59:06

Tests(8/10):


#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; double g[500][500]; double sum; bool vis[maxn]; int ct[maxn]; pi P[maxn]; void dfs(int x,double p,int cnt){ if(x>n*m){sum+=(cnt-1)*p;return;} if(vis[P[x].p2]){dfs(x+1,p,cnt);return;} vis[P[x].p2]=1;dfs(x+1,p*(1-g[P[x].p1][P[x].p2]),cnt+1);vis[P[x].p2]=0; if(ct[P[x].p2]+1==n){sum+=cnt*p*g[P[x].p1][P[x].p2];return;} ++ct[P[x].p2];dfs(x+1,p*g[P[x].p1][P[x].p2],cnt+1);--ct[P[x].p2]; } double cal(){ int ct=0; up(i,1,n)up(j,1,m)P[++ct]=m_p(i,j); double res=1e18; do { sum=0;dfs(1,1,1);res=min(res,sum); }while(next_permutation(P+1,P+ct+1)); return res; } double cal2(){ double A=1,M=1; up(i,2,n)M*=0.5,A+=M; double G=A/2;double s=A; up(i,2,m)A*=G,s+=A; return s; } void slv(){ n=read(),m=read(); bool fl=1;up(i,1,n)up(j,1,m){ int x=read();if(x!=50)fl=0; g[i][j]=x/100.0; } if(fl)printf("%.5f",cal2()); else printf("%.5f",cal()); }int main(){ // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }


测评信息: