Submission #9551520


Source Code Expand

Copy
#include<bits/stdc++.h>
#define ll double
#define fr(a,b) for(int i = a; i < b; i++)
#define mod 1000000007
#define triplet pair<int,pair<int,int>>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

ll dp[301][301][301];
ll solve(int one, int two, int three, int& n)
{
    if(one < 0 || two < 0 || three < 0)
        return 0;
    if(three == 0 && two == 0 && one == 0)
        return 0;

    if(dp[one][two][three] > 0)
        return dp[one][two][three];

    int remaining = one + two + three;
    ll exp_val = n+one*solve(one-1,two,three,n) + two*solve(one+1,two-1,three,n) +
                    three*solve(one,two+1,three-1,n);

    return dp[one][two][three] = exp_val/remaining;
}

int main(){
    int i,j,t,n,m,p,k;
    //fast_io;
    //cin>>t;
    t=1;
    while(t--)
    {
        cin>>n;
        int one=0,two=0,three=0;

        fr(0,n){
            int x;
            cin >> x;
            if(x == 1)one++;
            else if(x == 2)two++;
            else three++;
        }

        memset(dp, -1, sizeof dp);
        cout<<fixed<<setprecision(9)<<solve(one,two,three,n);
    }
    return 0;
}

Submission Info

Submission Time
Task J - Sushi
User kartik8800
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1194 Byte
Status AC
Exec Time 217 ms
Memory 213376 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 AC 53 ms 213248 KB
0_01 AC 53 ms 213248 KB
0_02 AC 53 ms 213248 KB
0_03 AC 53 ms 213248 KB
1_00 AC 53 ms 213248 KB
1_01 AC 53 ms 213248 KB
1_02 AC 53 ms 213248 KB
1_03 AC 53 ms 213376 KB
1_04 AC 56 ms 213376 KB
1_05 AC 217 ms 213376 KB
1_06 AC 55 ms 213376 KB
1_07 AC 134 ms 213376 KB
1_08 AC 193 ms 213376 KB
1_09 AC 147 ms 213376 KB
1_10 AC 143 ms 213376 KB
1_11 AC 178 ms 213376 KB
1_12 AC 185 ms 213376 KB
1_13 AC 209 ms 213376 KB
1_14 AC 208 ms 213376 KB
1_15 AC 214 ms 213376 KB
1_16 AC 213 ms 213376 KB
1_17 AC 216 ms 213376 KB