Advertisement
Dang_Quan_10_Tin

CANDY

Jul 9th, 2022
838
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 2e5 + 5;
  7. constexpr ll Inf = 1e17;
  8.  
  9. int n, m;
  10. int a[N][16], c[16], id[N];
  11. ll b[1 << 16];
  12.  
  13. void Read()
  14. {
  15.     cin >> n >> m;
  16.  
  17.     for (int i = 1; i <= n; ++i)
  18.         for (int j = 0; j < m; ++j)
  19.             cin >> a[i][j];
  20.     for (int j = 0; j < m; ++j)
  21.         cin >> c[id[j] = j];
  22. }
  23.  
  24. #define bit(i, x) (((x) >> (i)) & 1)
  25.  
  26. void Solve()
  27. {
  28.     for (int i = 1; i <= n; ++i)
  29.     {
  30.         sort(id, id + m, [&](const int &x, const int &y)
  31.              { return a[i][x] > a[i][y]; });
  32.  
  33.         int mask = 0;
  34.  
  35.         for (int j = 0; j < m; ++j)
  36.         {
  37.             b[mask] -= a[i][id[j]];
  38.             mask |= 1 << id[j];
  39.             b[mask] += a[i][id[j]];
  40.         }
  41.     }
  42.  
  43.     for (int i = 0; i < m; ++i)
  44.         for (int j = 0; j < (1 << m); ++j)
  45.             if (!bit(i, j))
  46.                 b[j] += b[j ^ (1 << i)];
  47.  
  48.     ll ans(Inf);
  49.  
  50.     for (int j = 1; j < (1 << m); ++j)
  51.     {
  52.         for (int i = 0; i < m; ++i)
  53.             if (bit(i, j))
  54.                 b[j] += c[i];
  55.  
  56.         ans = min(ans, b[j]);
  57.     }
  58.  
  59.     cout << ans;
  60. }
  61.  
  62. int32_t main()
  63. {
  64.     ios::sync_with_stdio(0);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.     Read();
  68.     Solve();
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement