Contest Duration: ~ (local time) (300 minutes)

Submission #11206860

Source Code Expand

Copy
```#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
using namespace std::chrono;
long long int p=1e9 +7;
int n;
bool compatibility[21][21];
ll ans[21][1ll<<21];
ll solve(int N,int left){
ll currans=0;//initialise with 0
return ans[N-1][left];
}
if(N==1){
for(int j=0;j<n;j++){
int x=1<<j;
if(left & x){//check if the jth women is left
if(compatibility[N-1][j]){
ans[N-1][left]=1;
return 1;//If they are compatible return 1
}
else{
ans[N-1][left]=0;
return 0;//If the last 2 aren't compatible return 0
}
}
}
}
for(int i=0;i<n;i++){
if(left & (1ll<<i)){//If the ith women is left
if(compatibility[N-1][i]){//If the 2 are compatible
currans+=solve(N-1,left - (1ll<<i));
//Find the number of pairs after pairing them
}
}
}
currans%=p;//mod p
ans[N-1][left]=currans;//memoise
return ans[N-1][left];
}
ll solve(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<(1ll<<n);j++){
ans[i][j]=-1;//memoisation initialisation
//ans[i][j] represents i people left and
//j is the bitmask for women left
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>compatibility[i][j];
}
}
return solve(n,(1<<n)-1);//all men available, all women available because all bits set in mask
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout<<solve()<<"\n";
}
```

#### Submission Info

Submission Time 2020-03-26 02:40:04+0900 O - Matching Everule C++14 (GCC 5.4.1) 100 1974 Byte AC 500 ms 344320 KB

#### Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 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
Case Name Status Exec Time Memory
0_00 2 ms 4352 KB
0_01 2 ms 6400 KB
0_02 1 ms 256 KB
0_03 434 ms 344320 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 86 ms 344320 KB
1_03 86 ms 344320 KB
1_04 106 ms 344320 KB
1_05 329 ms 344320 KB
1_06 361 ms 344320 KB
1_07 395 ms 344320 KB
1_08 469 ms 344320 KB
1_09 466 ms 344320 KB
1_10 500 ms 344320 KB
1_11 489 ms 344320 KB
1_12 494 ms 344320 KB