Advertisement
Guest User

Untitled

a guest
Apr 5th, 2020
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <ext/rope>
  5.  
  6. #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
  7. #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
  8. #define mod 998244353
  9. #define xx first
  10. #define yy second
  11. #define all(a) (a).begin(), (a).end()
  12. #define pb push_back
  13. #define ll long long
  14. #define pii pair<int,int>
  15. #define maxn 500005
  16.  
  17.  
  18.  
  19.  
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
  24. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26.  
  27. int n,k;
  28. int niz[maxn];
  29.  
  30. bool check(int x){
  31.     int pref = 0;
  32.     for(int l=0; l<=n; l++){
  33.         if(l != 0){
  34.             int staripref = pref;
  35.             pref |= niz[l];
  36.             if(pref == staripref)continue;
  37.         }
  38.         int ks = pref;
  39.         int r = n;
  40.         bool ima = 0;
  41.         for(;r>=l+1; r--){
  42.             ks |= niz[r];
  43.             if( (ks - x) == (ks^x)){
  44.                 ima = 1;
  45.                 break;
  46.             }
  47.         }
  48.         if(!ima)continue;
  49.         ks = 0;
  50.         int pomk = k;
  51.         pomk--;
  52.         for(int i=l+1; i<=r-1; i++){
  53.             ks |= niz[i];
  54.             if( (ks - x) == (ks^x)){
  55.                 pomk--;
  56.                 if(pomk == 0)return 1;
  57.                 ks = 0;
  58.             }
  59.         }
  60.     }
  61.     return 0;
  62. }
  63.  
  64.  
  65. int main()
  66. {
  67.  
  68.     ios_base::sync_with_stdio(false); cin.tie(0);
  69.     cin >> n >> k;
  70.     ff(i,1,n)cin >> niz[i];
  71.     if(k == 1){
  72.         int sta = 0;
  73.         ff(i,1,n)sta |= niz[i];
  74.         cout << sta << endl;
  75.         return 0;
  76.     }
  77.     int pref = 0;
  78.     fb(i,29,0){
  79.         bool sta = check(pref | (1<<i));
  80.         if(sta)pref |= (1<<i);
  81.     }
  82.     cout << pref << endl;
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement