fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // template {{{
  5. #define pb push_back
  6. #define eb emplace_back
  7. #define mp make_pair
  8. #define mt make_tuple
  9. #define lb lower_bound
  10. #define ub upper_bound
  11. #define f first
  12. #define s second
  13. #define resz resize
  14.  
  15. #define sz(x) int((x).size())
  16. #define all(x) (x).begin(), (x).end()
  17.  
  18. #define FOR(i, a, b) for (int i = (a); i < (b); i++)
  19. #define F0R(i, a) for (int i = 0; i < (a); i++)
  20. #define FORd(i, a, b) for (int i = (b)-1; i >= (a); i--)
  21. #define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
  22. #define trav(a, x) for (auto& a : x)
  23.  
  24. #define sort_by(x, y) sort(all(x), [&](const auto& a, const auto& b) { return y; })
  25.  
  26. using ll = long long;
  27. using vi = vector<int>;
  28. using vvi = vector<vi>;
  29. using vll = vector<ll>;
  30. using vvll = vector<vll>;
  31. using vb = vector<bool>;
  32. using vd = vector<double>;
  33. using vs = vector<string>;
  34.  
  35. using pii = pair<int, int>;
  36. using pll = pair<ll, ll>;
  37. using pdd = pair<double, double>;
  38.  
  39. using vpii = vector<pii>;
  40. using vpll = vector<pll>;
  41. using vpdd = vector<pdd>;
  42.  
  43. template<typename T> void ckmin(T& a, const T& b) { a = min(a, b); }
  44. template<typename T> void ckmax(T& a, const T& b) { a = max(a, b); }
  45.  
  46. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  47.  
  48. namespace __input {
  49.     template<class T1, class T2> void re(pair<T1,T2>& p);
  50.     template<class T> void re(vector<T>& a);
  51.     template<class T, size_t SZ> void re(array<T,SZ>& a);
  52.  
  53.     template<class T> void re(T& x) { cin >> x; }
  54.     void re(double& x) { string t; re(t); x = stod(t); }
  55.     template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
  56.         re(first); re(rest...);
  57.     }
  58.  
  59.     template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
  60.     template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
  61.     template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
  62. }
  63. using namespace __input;
  64.  
  65. namespace __output {
  66.     template<class T1, class T2> void pr(const pair<T1,T2>& x);
  67.     template<class T, size_t SZ> void pr(const array<T,SZ>& x);
  68.     template<class T> void pr(const vector<T>& x);
  69.     template<class T> void pr(const set<T>& x);
  70.     template<class T1, class T2> void pr(const map<T1,T2>& x);
  71.  
  72.     template<class T> void pr(const T& x) { cout << x; }
  73.     template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
  74.         pr(first); pr(rest...);
  75.     }
  76.  
  77.     template<class T1, class T2> void pr(const pair<T1,T2>& x) {
  78.         pr("{",x.f,", ",x.s,"}");
  79.     }
  80.     template<class T, bool pretty = true> void prContain(const T& x) {
  81.         if (pretty) pr("{");
  82.         bool fst = 1; for (const auto& a: x) pr(!fst?pretty?", ":" ":"",a), fst = 0;
  83.         if (pretty) pr("}");
  84.     }
  85.     template<class T> void pc(const T& x) { prContain<T, false>(x); pr("\n"); }
  86.     template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
  87.     template<class T> void pr(const vector<T>& x) { prContain(x); }
  88.     template<class T> void pr(const set<T>& x) { prContain(x); }
  89.     template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
  90.  
  91.     void ps() { pr("\n"); }
  92.     template<class Arg> void ps(const Arg& first) {
  93.         pr(first); ps();
  94.     }
  95.     template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
  96.         pr(first," "); ps(rest...);
  97.     }
  98. }
  99. using namespace __output;
  100.  
  101. #define TRACE(x) x
  102. #define __pn(x) pr(#x, " = ")
  103. #define pd(...) __pn((__VA_ARGS__)), ps(__VA_ARGS__), cout << flush
  104.  
  105. namespace __algorithm {
  106.     template<typename T> void dedup(vector<T>& v) {
  107.         sort(all(v)); v.erase(unique(all(v)), v.end());
  108.     }
  109.     template<typename T> typename vector<T>::const_iterator find(const vector<T>& v, const T& x) {
  110.         auto it = lower_bound(all(v), x); return it != v.end() && *it == x ? it : v.end();
  111.     }
  112.     template<typename T> size_t index(const vector<T>& v, const T& x) {
  113.         auto it = find(v, x); assert(it != v.end() && *it == x); return it - v.begin();
  114.     }
  115.  
  116.     template<typename T1, typename T2> typename vector<pair<T1, T2>>::iterator lower_bound(
  117.             const vector<pair<T1, T2>>& v, const T1& x) {
  118.         return lower_bound(all(v), x, [](pair<T1, T2> a, pair<T1, T2> b) { return a.f < b.f; });
  119.     }
  120.     template<typename T1, typename T2> typename vector<pair<T1, T2>>::iterator upper_bound(
  121.             const vector<pair<T1, T2>>& v, const T1& x) {
  122.         return upper_bound(all(v), x, [](pair<T1, T2> a, pair<T1, T2> b) { return a.f < b.f; });
  123.     }
  124. }
  125. using namespace __algorithm;
  126.  
  127. /*struct __monostate {
  128.     friend istream& operator>>(istream& is, const __attribute__((unused))__monostate& ms) { return is; }
  129.     friend ostream& operator<<(ostream& os, const __attribute__((unused))__monostate& ms) { return os; }
  130. } ms;
  131.  
  132. namespace __io {
  133.     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  134.     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  135.     void setIO(string s = "") {
  136.         ios_base::sync_with_stdio(0); cin.tie(0);
  137.         cout << setprecision(15);
  138.         if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
  139.     }
  140. }
  141. using namespace __io;*/
  142. // }}}
  143. const int N = 1e5+2;
  144. int t, n, k;
  145. int main()
  146. {
  147.     re(t);
  148.     while(t--)
  149.     {
  150.         re(n, k);
  151.         vll a(n+1), cnt(31);
  152.         for(int i = 1; i<=n; i++)
  153.         {
  154.             re(a[i]);
  155.             for(int j = 0; j<31; j++)
  156.                 if((a[i]&(1<<j)))
  157.                     cnt[j]++;
  158.         }
  159.         vector<vector<pll>> dp(31, vector<pll>(k+1, {0, 0}));
  160.         for(int i  = 0; i<=30; i++)
  161.         {
  162.             for(int x = 0; x<=k; x++)
  163.             {
  164.                 if(i==0)
  165.                 {
  166.                     if(x && cnt[i])
  167.                         dp[i][x] = {cnt[i], 1};
  168.                     continue;
  169.                 }
  170.                 if(x)
  171.                 {
  172.                     if((cnt[i]*(1ll<<i)+dp[i-1][x-1].f)>dp[i-1][x].f)
  173.                         dp[i][x].s = dp[i-1][x-1].s|(1ll<<i);
  174.                     else
  175.                         dp[i][x].s = dp[i-1][x].s;
  176.                     dp[i][x].f = max(cnt[i]*(1ll<<i)+dp[i-1][x-1].f, dp[i-1][x].f);
  177.                 }
  178.                 else
  179.                     dp[i][x] = dp[i-1][x];
  180.             }
  181.         }
  182.         ps(dp[30][k].s);
  183.     }
  184.         return 0;
  185. }
  186.  
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
1
4 1
1 1 1 1
stdout
copy 
1
https://ideone.com/cMdtRd
language:
C++14 (gcc 8.3)
created:
3 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!