Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <set>
  5. #include <map>
  6. #include <sstream>
  7. #include <queue>
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <fstream>
  11. #include <unordered_map>
  12. #include <cassert>
  13. #include <ctime>
  14.  
  15. #define lol long long
  16.  
  17. using namespace std;
  18.  
  19. const int INF = 1e9;
  20.  
  21. int dp[505][343 * 8];
  22. int precalc[343 * 8];
  23. vector<pair<int, int> > masks[8];
  24.  
  25. int diff(int a1, int b1)
  26. {
  27. return a1 > b1 ? a1 - b1 : 0;
  28. }
  29.  
  30. int diff(int mask1, int mask2, int a1, int a2, int a3, int a4, int a5, int a6)
  31. {
  32. int x = mask1 % 7;
  33. int y = mask1 / 7 % 7;
  34. int z = mask1 / 49 % 7;
  35.  
  36. int b1, b2, b3, b4, b5, b6;
  37. b1 = b2 = b3 = b4 = b5 = b6 = 0;
  38. (mask2 & 1 ? b1 : b6) = x;
  39. (mask2 & 2 ? b2 : b5) = y;
  40. (mask2 & 4 ? b3 : b4) = z;
  41. return diff(a1, b1) + diff(a2, b2) + diff(a3, b3) + diff(a4, b4) + diff(a5,
  42. b5) + diff(a6, b6);
  43. }
  44.  
  45. int main()
  46. {
  47. ios_base::sync_with_stdio(0);
  48.  
  49.  
  50. int n;
  51. cin >> n;
  52. vector<string> v(n + 1, "");
  53. vector<char> mx(n + 1, '0');
  54. for (int i = 1; i <= n; ++i)
  55. {
  56. cin >> v[i];
  57.  
  58. for (int j = 0; j < 7; ++j)
  59. mx[i] = max(mx[i], v[i][j]);
  60. }
  61.  
  62. for (int i = 0; i < 343; ++i)
  63. {
  64. int a1, a2, a3, a4, a5, a6;
  65. a1 = a2 = a3 = a4 = a5 = a6 = 0;
  66. int f = i % 7;
  67. int s = i / 7 % 7;
  68. int t = i / 7 / 7 % 7;
  69. for (int j = 0; j < 8; ++j)
  70. {
  71. int p = i * 8 + j;
  72. (j & 1 ? a1 : a6) = f;
  73. (j & 2 ? a2 : a5) = s;
  74. (j & 4 ? a3 : a4) = t;
  75. int k = 0;
  76. k += a1 * 1 + a2 * 2 + a3 * 3 + a4 * 4 + a5 * 5 + a6 * 6;
  77. k %= 7;
  78. precalc[p] = k;
  79. masks[k].push_back({p, a1 + a2 + a3 + a4 + a5 + a6});
  80. }
  81. }
  82.  
  83. for (int i = 1; i <= n; ++i)
  84. {
  85. for (int j = 0; j < 343 * 8; ++j)
  86. dp[i][j] = 1e9;
  87. }
  88.  
  89. for (int j = 0; j < 7; ++j)
  90. {
  91. if (v[1][j] == mx[1])
  92. {
  93. for (auto mask : masks[j])
  94. dp[1][mask.first] = mask.second;
  95. }
  96. }
  97.  
  98. for (int i = 1; i < n; ++i)
  99. {
  100. for (int j = 0; j < 343; ++j)
  101. {
  102. for (int j_ = 0; j_ < 8; ++j_)
  103. {
  104. if (dp[i][j * 8 + j_] != 1e9)
  105. {
  106. for (int nx_mask = 0; nx_mask < 49; ++nx_mask)
  107. {
  108.  
  109. for (int k = 0; k < 4; ++k)
  110. {
  111. int a1, a2, a3, a4, a5, a6;
  112. a1 = a2 = a3 = a4 = a5 = a6 = 0;
  113. int f = j % 7;
  114. int s = j / 7 % 7;
  115. (k & 1 ? a2 : a5) = f;
  116. (k & 2 ? a3 : a4) = s;
  117.  
  118. for (int jj = 0; jj < 7; ++jj)
  119. {
  120. if (v[i + 1][jj] == mx[i + 1])
  121. {
  122. int cur = (a2 * 2 + a3 * 3 + a4 * 4 + a5 * 5) % 7;
  123. // jj = cur + need % 7
  124. int need = (jj - cur + 7) % 7;
  125. {
  126. a1 = need;
  127. a6 = 0;
  128. int mask = (nx_mask * 7 + (a1 + a6)) * 8 + (k << 1) + 1;
  129. int d = diff(j, j_, a1, a2, a3, a4, a5, a6);
  130. dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][j * 8 + j_] + d);
  131. }
  132. {
  133. a1 = 0;
  134. a6 = 7 - need;
  135. int mask = (nx_mask * 7 + (a1 + a6)) * 8 + (k << 1);
  136. int d = diff(j, j_, a1, a2, a3, a4, a5, a6);
  137. dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][j * 8 + j_] + d);
  138. }
  139.  
  140. }
  141. }
  142. }
  143. }
  144. }
  145. }
  146. }
  147. }
  148.  
  149. cout << dp[3][49 * 8 + 4] << endl;
  150.  
  151. int mn = 1e9;
  152. for (int i = 0; i < 343 * 8; ++i)
  153. {
  154. mn = min(dp[n][i], mn);
  155. }
  156. cout << mn;
  157. }
  158.  
  159. /*
  160. *
  161. *
  162. *
  163. 6
  164. 9689331
  165. 1758824
  166. 3546327
  167. 5682494
  168. 9128291
  169. 9443696
  170.  
  171. 7
  172. 5941186
  173. 3871463
  174. 8156346
  175. 9925977
  176. 8836125
  177. 9999999
  178. 5987743
  179. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement