제출 #291810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291810		nicolaalexandra	Fishing Game (RMI19_fishing)	C++14	100 / 100	564 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>=1;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
                        int ok3 = 0;

                        if (nr_ab || nr_ac){

                            if (!tip_a){
                                if (nr_ab > 0){
                                    sol1 = nr_ab;
                                    nr_ab--;
                                    ok3 = 1;
                                } else continue;
                            } else {
                                if (nr_ac > 0){
                                    sol1 = nr_ac;
                                    nr_ac--, nr_bc++;
                                    ok3 = 1;
                                } else continue;

                            }

                        } else {
                            sol1 = 1; /// nu am ce sa dau mai departe
                            tip_a = 2;
                        }

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

                            /// B -> C
                            int ok2 = 0;

                            if (nr_bc || nr_ab){
                                if (!tip_b){
                                    if (nr_bc > 0){
                                        sol2 = nr_bc;
                                        nr_bc--;
                                        ok2 = 1;
                                    } else continue;
                                } else {
                                    if (nr_ab > 0){
                                        sol2 = nr_ab;
                                        nr_ab--, nr_ac++;
                                        ok2 = 1;
                                    } else continue;
                                }
                            } else {
                                sol2 = 1;
                                tip_b = 2;
                            }
                            //if (nr_ab < 0 || nr_ac < 0 || nr_bc < 0)
                              //  printf ("a");
                            for (int tip_c=0;tip_c<=1;tip_c++){

                                /// C -> A
                                int ok = 0;
                                if (nr_ac || nr_bc){
                                    if (!tip_c){
                                        if (nr_ac > 0){
                                            sol3 = nr_ac;
                                            nr_ac--;
                                            ok = 1;
                                        } else continue;
                                    } else {
                                        if (nr_bc > 0){
                                            sol3 = nr_bc;
                                            nr_bc--, nr_ab++;
                                            ok = 1;
                                        } else continue;
                                    }
                                } else {
                                    sol3 = 1;
                                    tip_c = 2;
                                }

                                if (nr_ab + nr_ac + nr_bc < i + j + k){
                                    //if (nr_ab < 0 || nr_ac < 0 || nr_bc < 0)
                                      //  printf ("a");
                                    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;
                                    //cout<<sol1*sol2*sol3<<"\n";
                                }

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

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

                        }

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

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

    return 0;
}

• Subtask 1: 100 / 100