Submission #291510

#	Time	Username	Problem	Language	Result	Execution time	Memory
291510		nicolaalexandra	Fishing Game (RMI19_fishing)	C++14	0 / 100	512 ms	117112 KiB

fishing

#include <bits/stdc++.h>
#define DIM 310
#define MOD 1000000007
using namespace std;

int dp[DIM][DIM][DIM],fa[DIM*2],fb[DIM*2],fc[DIM*3],a[DIM],b[DIM],c[DIM];
int t,n,i,j,k;

int main (){

    //ifstream cin ("fishing.in");
    //ofstream cout ("fishing.out");

    cin>>n>>t;
    for (;t--;){

        memset (fa,0,sizeof fa);
        memset (fb,0,sizeof fb);
        memset (fc,0,sizeof fc);

        for (i=1;i<=2*n;i++){
            cin>>a[i];
            fa[a[i]]++;
        }

        for (i=1;i<=2*n;i++){
            cin>>b[i];
            fb[b[i]]++;
        }
        for (i=1;i<=2*n;i++){
            cin>>c[i];
            fc[c[i]]++;
        }

        int nr_ab = 0, nr_ac = 0, nr_bc = 0;
        for (i=1;i<=3*n;i++){
            if (fa[i] && fb[i]) /// cate au in comun a si b
                nr_ab++;
            if (fa[i] && fc[i]) /// cate au in comun a si c
                nr_ac++;
            if (fb[i] && fc[i]) /// cate au in comun b si c
                nr_bc++;
        }

        memset (dp,0,sizeof dp);
        dp[nr_ab][nr_ac][nr_bc] = 1;
        for (int sum=nr_ab + nr_ac + nr_bc;sum>=0;sum--){
            for (i=0;i<=sum && i<=3*n;i++){
                for (j=0;i+j<=sum && j<=3*n;j++){
                    k = sum - i - j;

                    if (k > 3*n || !dp[i][j][k]) /// nu am calculat starea asta
                        continue;

                    /// A -> B -> C -> A

                    int nr_ab = i, nr_ac = j, nr_bc = k, sol1, sol2, sol3;

                    for (int tip_a=0;tip_a<=1;tip_a++){
                        /// A -> B
                        if (!tip_a){
                            sol1 = nr_ab;
                            nr_ab--;
                        } else {
                            sol1 = nr_ac;
                            nr_ac--, nr_bc++;
                        }

                        for (int tip_b=0;tip_b<=1 && sol1;tip_b++){

                            /// B -> C

                            if (!tip_b){
                                sol2 = nr_bc;
                                nr_bc--;
                            } else {
                                sol2 = nr_ab;
                                nr_ab--, nr_ac++;
                            }

                            for (int tip_c=0;tip_c<=1 && sol2;tip_c++){

                                /// C -> A
                                if (!tip_c){
                                    sol3 = nr_ac;
                                    nr_ac--;
                                } else {
                                    sol3 = nr_bc;
                                    nr_bc--, nr_ab++;
                                }

                                if (nr_ab + nr_ac + nr_bc < i + j + k && sol3 > 0){
                                    dp[nr_ab][nr_ac][nr_bc] += 1LL * dp[i][j][k] * sol1 % MOD * sol2 % MOD * sol3 % MOD;
                                    if (dp[nr_ab][nr_ac][nr_bc] >= MOD)
                                        dp[nr_ab][nr_ac][nr_bc] -= MOD;
                                }

                                (!tip_c) ? (nr_ac++) : (nr_bc++, nr_ab--);

                            }

                            (!tip_b) ? (nr_bc++) : (nr_ab++, nr_ac--);

                        }

                        /// reverse
                        (!tip_a) ? (nr_ab++) : (nr_ac++, nr_bc--);
                    }}}}

        cout<<dp[0][0][0]<<"\n";
    }




    return 0;
}

• Subtask 1: 0 / 100