261B - Maxim and Restaurant - CodeForces Solution

#include "bits/stdc++.h"
using ll = long long  ;
#define F first
#define S second
const ll mod = 998244353 ;
const ll N = 2e5 + 5 ;
using namespace std;
double fact[55];
ll n , p  , vis[55][55][55] , timer , a[55] , t = 1;
double dp[55][55][55];
double DP(ll i , ll take , ll sum , ll j)
{
    if(sum > p)return 0 ;
    if(i == n + 1)
    {
        if(sum + a[j] > p)
        {
          return take * fact[take] * fact[n - take - 1] / fact[n]  ;
        }
        return 0 ;
    }
    double &ret = dp[i][take][sum] ;
    if(vis[i][take][sum] == timer)return ret ;
    vis[i][take][sum] = timer ;
    ret =  0.0 ;
    if(i == j)return ret = DP(i + 1 , take , sum , j) ;
    ret += DP(i + 1 , take + 1 , sum + a[i] , j) ;
    ret += DP(i + 1 , take , sum , j) ;
    return ret ;
}
int main()
{
    //cin >> t ;
    while(t--)
    {
        fact[0] = 1.0 ;
        for(int i = 1 ; i <= 50 ; ++i)fact[i] = fact[i - 1]  * i ;
        cin >> n ;
        int sum = 0 ;
        for(int i = 1 ; i <= n ; ++i)cin >> a[i] , sum += a[i] ;
        cin >> p ;
        if(sum <= p){
            cout << n << "\n";
            return 0;
        }
        double ans = 0.0 ;
        for(int i = 1 ; i <= n ; ++i)
        {
            timer = timer + 1 ;
            ans += DP(1 , 0  , 0 , i) ;
        }
        cout << fixed << setprecision(10) << ans << "\n";

    }

}