SRM-613(Div-2) 1000

Problem Statement

Solution Analysis

Code:

#include<bits/stdc++.h>

using namespace std;
#define LL long long

vector<int>ff,ss;
LL n,k;

LL dp[59][1050][45];

LL f(LL i,LL mask,LL r)
{
    if(dp[i][mask][r]!=-1) return dp[i][mask][r];
    if(i==n)
    {
        LL p=__builtin_popcount(mask);
        if(p+r<=k) return 1;
        else return 0;
    }
    // not using i-th card
    LL res=f(i+1,mask,r);
    // using i-th card
    LL nmask=mask;
    LL nr=r;
    if(ff[i]>10) nr++;
    else nmask=nmask|(1<<(ff[i]-1));
    nmask=nmask|(1<<(ss[i]-1));
    res=res+f(i+1,nmask,nr);
    return dp[i][mask][r]=res;
}


class TaroCards
{
public:
	long long getNumber(vector <int> first, vector <int> second, int K)
	{
	    ff=first;
	    ss=second;
	    k=K;
	    n=ff.size();
	    memset(dp,-1,sizeof(dp));
	    return f(0,0,0);
	}
};

Advertisements
About

ACM Competitive Programmer

Posted in Favorite Problems, TopCoder

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: