fork(1) download
copy 
  1. #include <ext/pb_ds/assoc_container.hpp>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. using namespace __gnu_cxx;
  8.  
  9. /* clang-format off */
  10.  
  11. /* TYPES  */
  12. #define ll long long
  13. #define ld long double
  14. #define pii pair<int, int>
  15. #define pll pair<long long, long long>
  16. #define vi vector<int>
  17. #define vll vector<long long>
  18. #define vpii vector<pair<int, int>>
  19. #define vpii vector<pair<int, int>>
  20. #define vvpii vector<vector<pair<int, int>>>
  21. #define vpll vector<pair<long long, long long>>
  22. #define vvpll vector<vector<pair<long long, long long>>>
  23. #define vvi vector<vector<int>>
  24. #define vvll vector<vector<long long>>
  25. #define mii map<int, int>
  26. #define si set<int>
  27. #define sc set<char>
  28. #define vd vector<double>
  29. #define vvd vector<vector<double>>
  30.  
  31.  
  32. /* FUNCTIONS */
  33. #define feach(el, v) for(auto &el: v)
  34. #define rep(i, n) for(int i=0;i<n;i++)
  35. #define reprv(i, n) for(int i=n-1;i>=0;i--)
  36. #define reps(i, s, e) for(int i=s;i<e;i++)
  37. #define reprve(i, e, s) for(int i=e-1;i>=s;i--)
  38. #define repe(x, y) for (auto &x: y)
  39. #define repe2(x, a, y) for (auto &[x,a]: y)
  40.  
  41. #define pb push_back
  42. #define eb emplace_back
  43.  
  44.  
  45.  
  46. #define IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  47. #pragma GCC target("popcnt")
  48. #define vct vector
  49.  
  50. int cntLeq(vll &v, ll x) { return std::upper_bound(v.begin(), v.end(), x) - v.begin(); }
  51. int cntLess(vll &v, ll x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); }
  52. int cntGreater(vll &v, ll x) { return v.end() - std::upper_bound(v.begin(), v.end(), x); }
  53. int cntGeq(vll &v, ll x) { return v.end() - std::lower_bound(v.begin(), v.end(), x); }
  54.  
  55. vll buildPref(vll &v) {
  56.     int n = v.size(); vll pref(n);
  57.     rep(i, n) pref[i] = v[i] + (i ? pref[i - 1] : 0);
  58.     return pref;
  59. }
  60. ll getPrefSum(vll &pref, int l, int r) {
  61.     if (l > r) return 0;
  62.     return pref[r] - (l ? pref[l - 1] : 0);
  63. }
  64.  
  65. vi dx = {0,0,-1,1}, dy = {-1,1,0,0};
  66.  
  67. int popcnt(int i) { return __builtin_popcountll(i); }
  68. int popcnt(long long i) { return __builtin_popcountll(i); }
  69.  
  70. template<typename T>inline void chmax(T &a,T b){a=max(a,b);}
  71. template<typename T>inline void chmin(T &a,T b){a=min(a,b);}
  72.  
  73. void vectorCoordinateCompression(vll &v) {
  74.     std::sort(v.begin(), v.end());
  75.     v.erase(std::unique(v.begin(), v.end()), v.end());
  76. }
  77.  
  78. int getVectorCompressed(ll val, vll &v) { return lower_bound(v.begin(), v.end(), val) - v.begin(); }
  79.  
  80. bool outOfGrid(int x, int y, int n, int m) { return x < 0 || x >= n || y < 0 || y >= m; }
  81.  
  82. //////////////////////////////////////////////////////////////////////////
  83. #define int long long int
  84.  
  85. vi zeta(vi f, int n) {
  86.     rep(i, n) rep(mask, (1 << n)) if ((mask & (1 << i))) f[mask] += f[mask ^ (1 << i)];
  87.     return f;
  88. }
  89.  
  90. int MAXPW = 10, MAXV = (1 << 10);
  91.  
  92. int getMask(string &s) {
  93.     int ans = 0;
  94.     repe(ch, s) ans |= (1 << (ch - 'a'));
  95.     return ans;
  96. }
  97.  
  98. int solution(vector<string> &s, int k) {
  99.     vi masks(MAXV);
  100.     repe(str, s) masks[getMask(str)]++;
  101.  
  102.     vi sos = zeta(masks, MAXPW);
  103.  
  104.     int ans = 0;
  105.     rep(i, MAXV) if (popcnt(i) <= k) ans = max(ans, sos[i]);
  106.     return ans;
  107. }
  108.  
  109. signed main() {
  110.     IO;
  111.  
  112.     vector<string> s1 = {"abc", "abb", "cb", "a", "bbb"};
  113.     cout << solution(s1, 2) << endl;
  114.  
  115.     vector<string> s2 = {"adf", "jjbh", "jcgj", "eijj", "adf"};
  116.     cout << solution(s2, 3) << endl;
  117.  
  118.     vector<string> s3 = {"abcd", "efgh"};
  119.     cout << solution(s3, 3) << endl;
  120.  
  121.     vector<string> s4 = {"bd", "edf", "fde", "dge", "abcd"};
  122.     cout << solution(s4, 4) << endl;
  123. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
2
0
3
https://ideone.com/9tbH9A
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

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!