fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef SG
  5. 	#include <debug.h>
  6. #else
  7. 	#define show(...)
  8. 	#define debug(...)
  9. 	#define deepen(...)
  10. 	#define timer(...)
  11. #endif
  12.  
  13. #define ARG4(_1,_2,_3,_4,...) _4
  14.  
  15. #define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
  16. #define forn2(i,n) forn3 (i, 0, n)
  17. #define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)
  18.  
  19. #define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
  20. #define ford2(i,n) ford3 (i, 0, n)
  21. #define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)
  22.  
  23. #define ve vector
  24. #define pa pair
  25. #define tu tuple
  26. #define mp make_pair
  27. #define mt make_tuple
  28. #define pb push_back
  29. #define fs first
  30. #define sc second
  31. #define all(a) (a).begin(), (a).end()
  32. #define sz(a) ((int)(a).size())
  33.  
  34. typedef long double ld;
  35. typedef long long ll;
  36. typedef unsigned long long ull;
  37. typedef unsigned int ui;
  38. typedef unsigned char uc;
  39. typedef pa<int, int> pii;
  40. typedef pa<int, ll> pil;
  41. typedef pa<ll, int> pli;
  42. typedef pa<ll, ll> pll;
  43. typedef ve<int> vi;
  44.  
  45. const ld pi = 3.1415926535897932384626433832795l;
  46.  
  47. template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
  48. template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
  49. template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}
  50.  
  51. const int N = 32;
  52. const int M = 32;
  53.  
  54. struct Input {
  55. 	int m;
  56. 	ll q[M];
  57. 	ui mskl[M], mskr[M];
  58.  
  59. 	bool read () {
  60. 		int n;
  61. 		if (!(cin >> n >> m)) {
  62. 			return 0;
  63. 		}
  64. 		forn (i, m) {
  65. 			string s;
  66. 			cin >> s >> q[i];
  67. 			mskl[i] = ~0u;
  68. 			mskr[i] = 0u;
  69. 			forn (j, n) {
  70. 			    mskl[i] -= 1ull << j;
  71. 				mskl[i] += ui(s[j] == '0' || s[j] == '?') << j;
  72. 				mskr[i] += ui(s[j] == '1' || s[j] == '?') << j;
  73. 			}
  74. 		}
  75. 		return 1;
  76. 	}
  77.  
  78. 	void init (const Input &input) {
  79. 		*this = input;
  80. 	}
  81. };
  82.  
  83. struct Data: Input {
  84. 	ll ans;
  85.  
  86. 	void write () {
  87. 		printf("%" PRId64 "\n", ans);
  88. 	}
  89.  
  90. 	virtual void solve () {}
  91.  
  92. 	virtual void clear () {
  93. 		*this = Data();
  94. 	}
  95. };
  96.  
  97. struct Solution: Data {
  98. 	ll calc (int k, ui l, ui r, int cnt) {
  99. 		if (!k) {
  100. 			return 0;
  101. 		}
  102. 		ui l1 = l & mskl[k - 1];
  103. 		ui r1 = r & mskr[k - 1];
  104. 		if (~(l1 | r1)) {
  105. 			return calc(k - 1, l, r, cnt);
  106. 		}
  107. 		int cnt1 = __builtin_popcount(l1 & r1);
  108. 		ll res = q[k - 1] << cnt1;
  109. 		if (cnt1 == cnt) {
  110. 			return res;
  111. 		}
  112. 		if (cnt1 == cnt - 1) {
  113. 			return res + calc(k - 1, r1 ^ l ^ r, l1 ^ l ^ r, cnt - 1);
  114. 		}
  115. 		return res + calc(k - 1, l, r, cnt) - calc(k - 1, l1, r1, cnt1);
  116. 	}
  117.  
  118. 	void solve () {
  119. 		timer();
  120. 		ans = calc(m, ~0u, ~0u, 32);
  121. 	}
  122.  
  123. 	void clear () {
  124. 	}
  125. };
  126.  
  127. Solution sol;
  128.  
  129. int main () {
  130. 	cout.setf(ios::showpoint | ios::fixed);
  131. 	cout.precision(20);
  132. #ifdef SG
  133. 	freopen("input.txt", "r", stdin);
  134. //	freopen("output.txt", "w", stdout);
  135. 	while (sol.read()) {
  136. 		sol.solve();
  137. 		sol.write();
  138. 		sol.clear();
  139. 	}
  140. #else
  141. //	freopen("", "r", stdin);
  142. //	freopen("", "w", stdout);
  143. 	sol.read();
  144. 	sol.solve();
  145. 	sol.write();
  146. #endif
  147. 	return 0;
  148. }
  149.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gIFTLT
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!