1017D - The Wu

I write a solution of O(4^n), and it gets TLE on test 4. I found a code which is also O(4^n) and passed in 300ms, deleted three blocks of my code, and insert 3 blocks from another code and then, a miracle happened — it gets TLE.

My code is here:

// Problem: D. The Wu
// Contest: Codeforces - Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)
// URL: https://mirror.codeforces.com/problemset/problem/1017/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

int w[15], cnt[4100];
int ans[4100][105];

void dfs(int u, int v, int n, int pos, int sum) {
	if (pos == n) {
		ans[u][min(sum, 101)] += cnt[v];
		return;
	}
	int x = (u >> pos) & 1;
	dfs(u, v | (x << pos), n, pos + 1, sum + w[pos]);
	dfs(u, v | ((x ^ 1) << pos), n, pos + 1, sum);
}

int main() {
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 0; i < n; i++) {
		scanf("%d", &w[n - i - 1]);
	}
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		int x = 0;
		for (char ch : s) {
			x = (x << 1) + (ch == '1');
		}
		cnt[x]++;
	}
	for (int i = 0; i < (1 << n); i++) {
		dfs(i, 0, n, 0, 0);
		for (int j = 1; j <= 100; j++) {
			ans[i][j] += ans[i][j - 1];
		}
	}
	while (q--) {
		string s;
		int lim;
		cin >> s >> lim;
		int x = 0;
		for (char ch : s) {
			x = (x << 1) + (ch == '1');
		}
		printf("%d\n", ans[x][lim]);
	}
}