Submission #4536104

---

Source Code Expand

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second

using namespace std;

using ld = long double;
using ll = long long int;

const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; assert(scanf("%lld", &x) == 1); return x;}
ld fin(){double x; assert(scanf("%lf", &x) == 1); return x;}
char yuyushiki[1000010]; string stin(){assert(scanf("%s", yuyushiki) == 1); return yuyushiki;}

// head

int main(){

  ll n = in();
  ll m = in();
  vector<ll> a(m);
  REP(i, m){
    a[i] = in();
  }
  vector<vector<ll>> to(n, vector<ll>(n, 0));
  vector<ll> cur(n, 0);
  for(ll i = m-1; i >= 0; i--){
    REP(j, n){
      if(a[i] != j){
        to[j][a[i]] += cur[j];
      }
    }
    cur[a[i]]++;
  }

  vector<ll> dp(PW(n), INFLL);
  dp[0] = 0;
  
  REP(i, PW(n)){
    REP(j, n){
      if(!(i & PW(j))){
        ll nd = 0;
        ll ni = i | PW(j);
        REP(k, n){
          if(!(i & PW(k))){
            nd += to[j][k];
          }
        }
        chmin(dp[ni], dp[i] + nd);
      }
    }
  }

  cout << dp[PW(n)-1] << endl;
  
  return 0;
}

Submission Info

Judge Result