Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <vector>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <ctime>
  12.  
  13. #define pb push_back
  14. #define ll long long
  15. #define mp make_pair
  16. #define f first
  17. #define s second
  18. #define pii pair < int, int >
  19. #define ull unsigned long long
  20. #define pll pair < ll, ll >
  21. #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
  22. #define all(s) s.begin(), s.end()
  23. #define sz(a) (int)a.size()
  24.  
  25. const int inf = (1ll << 30) - 1;
  26. const int maxn = (int) 1e5 + 10;
  27.  
  28. using namespace std;
  29.  
  30. int dp[(1<<20)+ 10][10 + 3];
  31. int a[100100];
  32. int prv[100100];
  33. int k[100100];
  34. int mx[100100];
  35. int cnt[(1<<10) + 10];
  36. int n;
  37. void solve(){
  38. scanf("%d", &n);
  39. for(int i = 1; i <= n; i++){
  40. scanf("%d", &a[i]);
  41. }
  42. for(int i = 1; i <= n; i++){
  43. scanf("%d", &k[i]);
  44. }
  45. for(int i = 0; i < (1<<10); i++)
  46. cnt[i] = __builtin_popcount(i);
  47.  
  48. for(int i = 1; i <= n; ++i){
  49. int x = a[i] & ((1<<10)-1);
  50. int y = (a[i] >> 10) & ((1<<10)-1);
  51. int &cur = mx[i];
  52. int &ind = prv[i];
  53. for(int mask = 0; mask < (1<<10); mask++){
  54. int K = k[i] - cnt[mask & y];
  55. if(K < 0 || K > 10) continue;
  56. int &cc = dp[(mask<<10)|x][K];
  57. if(mx[cc] > cur){
  58. cur = mx[cc];
  59. ind = cc;
  60. }
  61. }
  62. cur++;
  63.  
  64. for(int mask = 0; mask < (1<<10); ++mask){
  65. int K = cnt[mask & x];
  66. int &cc = dp[(y<<10)|mask][K];
  67. if(mx[cc] < cur){
  68. cc = i;
  69. }
  70. }
  71. }
  72. int j = 0;
  73. for(int i = 1; i <= n; i++){
  74. if(mx[j] < mx[i]){
  75. j = i;
  76. }
  77. }
  78. vector<int> ans;
  79. while(j){
  80. ans.pb(j);
  81. j = prv[j];
  82. }
  83. reverse(all(ans));
  84. printf("%d\n", ans.size());
  85. for(int i = 0; i < ans.size(); i++){
  86. if(i) printf(" ");
  87. printf("%d", ans[i]);
  88. }
  89. printf("\n");
  90. }
  91.  
  92. int main () {
  93. freopen("subsequence.in", "r", stdin);
  94. freopen("subsequence.out", "w", stdout);
  95. int t=1;
  96. //scanf("%d", &t);
  97. for(int i=1; i <= t; i++){
  98. //printf("Case #%d\n", i);
  99. solve();
  100. }
  101.  
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement