fork download 
  1.  
  2. #include<bits/stdc++.h>
  3. #define X first
  4. #define Y second
  5. #define all(x) begin(x), end(x)
  6. #define FOR(i, a, b) for(int i = (a); i <= (b); i++)
  7. #define FORD(i, b, a) for(int i = (b); i >= (a); i--)
  8. #define REP(i, a, b) for (int i = (a); i < (b); i++)
  9. #define mxx max_element
  10. #define mnn min_element
  11. #define SQR(x) (1LL * (x) * (x))
  12. #define MASK(i) (1LL << (i))
  13. #define Point Vector
  14. #define left Left
  15. #define right Right
  16. #define div Div
  17.  
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef double db;
  23. typedef long double ld;
  24. typedef pair<db, db> pdb;
  25. typedef pair<ld, ld> pld;
  26. typedef pair<int, int> pii;
  27. typedef pair<int, pii> piii;
  28. typedef pair<ll, ll> pll;
  29. typedef pair<ll, pll> plll;
  30. typedef pair<ll, int> pli;
  31. typedef pair<ll, pii> plii;
  32.  
  33. template<class A, class B>
  34.     bool maximize(A& x, B y) {
  35.         if (x < y) return x = y, true; else return false;
  36.     }
  37. template<class A, class B>
  38.     bool minimize(A& x, B y) {
  39.         if (x > y) return x = y, true; else return false;
  40.     }
  41.  
  42. /* END OF TEMPLATE */
  43.  
  44. const int N = 1e5 + 7;
  45. const int M = 16;
  46.  
  47. int Q, n, m, a[N];
  48.  
  49. long long cost[M][M];
  50.  
  51. void build_cost() {
  52.     for (int i = 0; i < m; i++)
  53.         for (int j = 0; j < m; j++) cost[i][j] = 0;
  54.     for (int y = 0; y < m; y++) {
  55.         int cnt_y = 0;
  56.         for (int i = 1; i <= n; i++)
  57.             if (a[i] == y) cnt_y++; else cost[y][a[i]]+=cnt_y;
  58.     }
  59. }
  60.  
  61. long long dp[MASK(M)], sum[M];
  62. int cnt[M];
  63.  
  64. void solve() {
  65.     cin>>n>>m;
  66.     memset(sum, 0, sizeof(sum));
  67.     memset(cnt, 0, sizeof(cnt));
  68.     for (int i = 1; i <= n; i++) {
  69.         cin>>a[i];
  70.         a[i]--;
  71.         sum[a[i]]+=i;
  72.         cnt[a[i]]++;
  73.     }
  74.     build_cost();
  75.     for (int mask = 0; mask < MASK(m); mask++) dp[mask] = 1e18;
  76.     dp[0] = 0;
  77.     for (int mask = 0; mask < MASK(m); mask++) {
  78.         for (int x = 0; x < m; x++)
  79.             if (((mask >> x) & 1) == 0) {
  80.                 long long chi_phi = sum[x] - cnt[x] - 1LL * cnt[x] * (cnt[x] - 1) / 2;
  81.                 for (int y = 0; y < m; y++)
  82.                     if (((mask >> y) & 1) == 1) chi_phi-=cost[y][x];
  83.                 minimize(dp[mask | MASK(x)], dp[mask] + chi_phi);
  84.             }
  85.     }
  86.     cout<<dp[MASK(m) - 1]<<"\n";
  87. }
  88.  
  89. int main() {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     int Q = 0;
  93.     cin>>Q;
  94.     while (Q--) solve();
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/d0l9TP
language:
C++14 (gcc 8.3)
created:
10 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!