Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- constexpr int N = 2e5 + 5;
- constexpr ll Inf = 1e17;
- int n, m;
- int a[N][16], c[16], id[N];
- ll b[1 << 16];
- void Read()
- {
- cin >> n >> m;
- for (int i = 1; i <= n; ++i)
- for (int j = 0; j < m; ++j)
- cin >> a[i][j];
- for (int j = 0; j < m; ++j)
- cin >> c[id[j] = j];
- }
- #define bit(i, x) (((x) >> (i)) & 1)
- void Solve()
- {
- for (int i = 1; i <= n; ++i)
- {
- sort(id, id + m, [&](const int &x, const int &y)
- { return a[i][x] > a[i][y]; });
- int mask = 0;
- for (int j = 0; j < m; ++j)
- {
- b[mask] -= a[i][id[j]];
- mask |= 1 << id[j];
- b[mask] += a[i][id[j]];
- }
- }
- for (int i = 0; i < m; ++i)
- for (int j = 0; j < (1 << m); ++j)
- if (!bit(i, j))
- b[j] += b[j ^ (1 << i)];
- ll ans(Inf);
- for (int j = 1; j < (1 << m); ++j)
- {
- for (int i = 0; i < m; ++i)
- if (bit(i, j))
- b[j] += c[i];
- ans = min(ans, b[j]);
- }
- cout << ans;
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement