Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PB push_back
#define PPB pop_back
#define MK make_pair
#define ALL(V) V.begin(), V.end()
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
typedef pair<int, pii> pipii;
constexpr int INF = 1LL << 61;
//constexpr int MOD = 1000000007;
constexpr int MAX_N = 100005;
int n, m, mem[1 << 22], cnt[1 << 22], a[MAX_N], cnttmp[22];
int imos[22][MAX_N];
int Solve(int mask) {
if (mem[mask] != -1) return mem[mask];
if (cnt[mask] == n) return 0;
int res = INF;
for (int i = 1; i <= m; ++i) {
if (1 << i & mask) continue;
int s = (cnt[mask] == 0) ? 0 : imos[i][cnt[mask] - 1];
int temp = cnttmp[i] - (imos[i][cnt[mask] + cnttmp[i] - 1] - s);
res = min(res, Solve(mask + (1 << i)) + temp);
}
return mem[mask] = res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
imos[a[i]][i]++;
cnttmp[a[i]]++;
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
imos[j][i + 1] += imos[j][i];
}
}
for (int i = 0; i < (1 << m + 1); ++i) {
for (int j = 1; j <= m; ++j) {
if (1 << j & i)
cnt[i] += cnttmp[j];
}
}
memset(mem, -1, sizeof(mem));
cout << Solve(0) << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment