2017-yo-t4.cpp

#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;
}