fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
  4. #define forn(i, n) for(int i = 0; i < (int)(n); i++)
  5. #define for1(i, n) for(int i = 1; i <= (int)(n); i++)
  6. #define all(x) (x).begin(), (x).end()
  7. #define clr(x) memset(x, 0, sizeof(x))
  8. #define pb push_back
  9. #define mp make_pair
  10. #define prev asdfsdf
  11. #define fi first
  12. #define se second
  13.  
  14. using namespace std;
  15. typedef long double ld;
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. typedef pair<int, int> PII;
  19. typedef pair<int, int> pii;
  20. typedef vector<int> vi;
  21. typedef long long i64;
  22.  
  23. int nxt() {
  24. 	int x;
  25. 	scanf("%d", &x);
  26. 	return x;
  27. }
  28.  
  29.  
  30. ull q[35][1 << 16];
  31. ull cur[35][1 << 16];
  32.  
  33. #define set asfkjskdfj
  34.  
  35. void set(int v, int p) {
  36. 	q[v][p >> 6] |= 1ull << (p & 63);
  37. }
  38.  
  39. struct node {
  40. 	node *ch[2];
  41. 	int mul;
  42.  
  43. 	node() {
  44. 		clr(ch);
  45. 	}
  46. };
  47.  
  48. node* root;
  49.  
  50. int m;
  51.  
  52. void add(ull mask, long long x) {
  53. 	node * cur = root;
  54. 	for (int i = m - 1; i >= 0; --i) {
  55. 		int bit = (mask >> i) & 1ull;
  56. 		if (!cur->ch[bit]) {
  57. 			cur->ch[bit] = new node();
  58. 		}
  59. 		cur = cur->ch[bit];
  60. 	}
  61. 	cur->mul = x;
  62. }
  63.  
  64. long long val[100];
  65.  
  66. long long ans = 0;
  67.  
  68. int SI;
  69. int r;
  70.  
  71. void go(node *root, int d, long long v) {
  72. 	if (!root->ch[0] && !root->ch[1]) {
  73. 		ans += v * root->mul;
  74. 		return;
  75. 	}
  76.  
  77. 	if (root->ch[0]) {
  78. 		memcpy(cur[d + 1], cur[d], SI);
  79. 		go(root->ch[0], d + 1, v);
  80. 	}
  81. 	if (root->ch[1]) {
  82. 		int cnt = 0;
  83. 		int i = m - 1 - d;
  84. 		for (int j = 0; j < r; ++j) {
  85. 			cur[d + 1][j] = q[i][j] | cur[d][j];
  86. 			cnt += __builtin_popcountll(cur[d + 1][j] ^ cur[d][j]);
  87. 		}
  88. 		go(root->ch[1], d + 1, v + val[i] * cnt);
  89. 	}
  90. }
  91.  
  92. void solve() {
  93. 	int n = nxt();
  94. 	m = nxt();
  95.  
  96. 	string msk[m];
  97.  
  98. 	for (int i = 0; i < m; ++i) {
  99. 		cin >> msk[i] >> val[i];
  100. 	}
  101.  
  102. 	int o[n];
  103. 	iota(o, o + n, 0);
  104. 	random_shuffle(o, o + n);
  105.  
  106. 	for (int i = 0; i < m; ++i) {
  107. 		string q(n, '0');
  108. 		for (int j = 0; j < n; ++j) {
  109. 			q[o[j]] = msk[i][j];
  110. 		}
  111. 		msk[i] = q;
  112. 	}
  113.  
  114. 	int k = min(n, 16);
  115. 	int v = n - k;
  116.  
  117. 	map <ull, int> cnt;
  118.  
  119. 	for (int t = 0; t < m; ++t) {
  120. 		for (int i = 0; i < (1 << k); ++i) {
  121. 			int ok = 1;
  122. 			for (int T = 0; T < k; ++T) {
  123. 				int bit = (i >> T) & 1;
  124. 				if (msk[t][T + v] != '?' && msk[t][T + v] != '0' + bit) {
  125. 					ok = 0;
  126. 					break;
  127. 				}
  128. 			}
  129. 			if (ok) set(t, i);
  130. 		}
  131. 	}
  132.  
  133. 	for (int i = 0; i < (1 << v); ++i) {
  134. 		ull mask = (1ull << m) - 1;
  135.  
  136. 		for (int j = 0; j < v; ++j) {
  137. 			int bit = (i >> j) & 1;
  138. 			for (int k = 0; k < m; ++k) {
  139. 				if (msk[k][j] != '?' && msk[k][j] != '0' + bit) {
  140. 					mask &= ~(1ull << k);
  141. 				}
  142. 			}
  143. 		}
  144. 		cnt[mask] += 1;
  145. 	}
  146.  
  147. 	r = ((1 << k) + 63) / 64;
  148.  
  149. 	SI = r * sizeof(ull);
  150.  
  151. 	root = new node();
  152.  
  153. 	for (auto p : cnt) {
  154. 		ull msk = p.fi;
  155. 		add(msk, p.se);
  156. 	}
  157.  
  158. 	go(root, 0, 0);
  159.  
  160. 	cout << ans << "\n";
  161. }
  162. int main()
  163. {
  164. #ifdef LOCAL
  165. 	freopen("input.txt", "r", stdin);
  166. #endif
  167. 	int t = 1;
  168. 	while (t--) solve();
  169. 	return 0;
  170. }
Runtime error #stdin #stdout 0s 39304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zX7bMI
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!