Advertisement
turmax

Untitled

Feb 23rd, 2022
637
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.69 KB | None | 0 0
  1. #pragma GCC optimize("O3","unroll-loops")
  2. #pragma GCC target("avx2")
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. #define int long long
  7. const int maxn=5e5+5;
  8. int cnt[1<<20];
  9. int col[maxn];
  10. int mask[maxn];
  11. int32_t main()
  12. {
  13. ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  14. mt19937 rnd(228228);
  15. int n,m;
  16. cin>>n>>m;
  17. set <int> moms1;
  18. vector <int> moms;
  19. vector <int> a[n];for(int i=0;i<n;++i) {a[i].resize(m);for(auto &h:a[i]) cin>>h; for(auto h:a[i]) moms1.insert(h); int w;cin>>w;a[i].push_back(w);}
  20. for(auto h:moms1) moms.push_back(h);
  21. for(int i=0;i<n;++i)
  22. {
  23. for(int j=0;j<m;++j)
  24. {
  25. int pos=lower_bound(moms.begin(),moms.end(),a[i][j])-moms.begin();
  26. a[i][j]=pos;
  27. }
  28. }
  29. int ans=1e18;
  30. for(int it=0;it<35;++it)
  31. {
  32. for(int j=0;j<moms.size();++j)
  33. {
  34. col[j]=(rnd()%20);
  35. }
  36. for(int j=0;j<(1<<20);++j) cnt[j]=1e18;
  37. for(int i=0;i<n;++i)
  38. {
  39. mask[i]=0;
  40. for(int j=0;j<m;++j)
  41. {
  42. mask[i] |= (1LL<< col[a[i][j]]);
  43. }
  44. cnt[mask[i]]=min(cnt[mask[i]],a[i].back());
  45. }
  46. int n1=20;
  47. for(int i=0;i<n1;++i)
  48. {
  49. for(int mask=0;mask<(1<<n1);++mask)
  50. {
  51. if(mask & (1<<i))
  52. {
  53. cnt[mask]=min(cnt[mask],cnt[mask-(1<<i)]);
  54. }
  55. }
  56. }
  57. for(int mask=0;mask<(1<<n1);++mask)
  58. {
  59. ans=min(ans,cnt[mask]+cnt[(1<<n1)-1-mask]);
  60. }
  61. }
  62. if(ans==1e18) {cout<<(-1);return 0;}
  63. cout<<ans;
  64. return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement