fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. #define pii pair<int,int>
  9. #define sz(x) (int)(x).size()
  10. const int N = 21;
  11. const int mod = 1e9 + 7;
  12.  
  13. #define BIT(mask, x) ((mask >> (x)) & 1)
  14. int n, m, a[1000005], cnt[N], f[N][N];
  15. ll dp[1 << N];
  16. signed main() {
  17.     freopen("game.inp","r",stdin);
  18.     freopen("game.out","w",stdout);
  19.     ios::sync_with_stdio(0);
  20.     cin.tie(0);
  21.  
  22.     while(cin >> n >> m){
  23.         if (n == 0 && m == 0) break;
  24.         for(int i = 1; i <= n; ++i) cin >> a[i];
  25.         memset(cnt, 0, sizeof cnt);
  26.         memset(f, 0, sizeof f);
  27.         for(int mask = 0; mask < (1 << m); ++mask) dp[mask] = 1e18;
  28.         dp[0] = 0;
  29.         for(int i = 1; i <= n; ++i){
  30.             for(int j = 1; j <= m; ++j) f[j][a[i]] += cnt[j];
  31.             ++cnt[a[i]];
  32.         }
  33.         for(int mask = 0; mask < (1 << m); ++mask){
  34.             for(int i = 0; i < m; ++i){
  35.                 if (!BIT(mask, i)){
  36.                     int tol = 0;
  37.                     for(int j = 0; j < m; ++j){
  38.                         if (j != i && !BIT(mask, j)) tol += f[j + 1][i + 1];
  39.                     }
  40.                     dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask] + tol);
  41.                 }
  42.             }
  43.         }
  44.         cout << dp[(1 << m) - 1] << '\n';
  45.     }    
  46. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/af953X
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!