Submission #456423

#	Time	Username	Problem	Language	Result	Execution time	Memory
456423		asdf1234coding	Global Warming (CEOI18_glo)	C++14	0 / 100	2 ms	460 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define MOD (ll) (1e9+7)

int compatible[21][21];
int dp[1<<21];

int main() {
    ios_base::sync_with_stdio(false);
    ll n; cin>>n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin>>compatible[i][j];
        }
    }
    dp[0]=1;
    for(int subset = 0; subset<(1<<n); subset++) {
        int numberOfPairs = __builtin_popcount(subset); // number of women that are paired already
        for(int woman=0; woman<n; woman++) {
            if((subset&(1<<woman))) continue; // if this woman is already paired, continue
            if(!compatible[numberOfPairs][woman]) continue; // if this woman is not compatible with the next man, continue
            dp[subset | (1<<woman)] += dp[subset]; // add woman to subset and update dp value
            dp[subset | (1<<woman)] %= MOD;
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25