fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 1e5;
  12. const int maxk = 20;
  13. const ll INF = 1e18;
  14.  
  15. int n, k, l = 1, r = 0;
  16. ll a[maxn + 10], dp[maxn + 10][maxk + 10], cnt[maxn + 10], quantity = 0;
  17.  
  18. void add(int p)
  19. {
  20.     quantity += cnt[a[p]];
  21.     cnt[a[p]]++;
  22. }
  23. void del(int p)
  24. {
  25.     cnt[a[p]]--;
  26.     quantity -= cnt[a[p]];
  27. }
  28. ll cost(int ql, int qr)
  29. {
  30.     while (l < ql) del(l++);
  31.     while (l > ql) add(--l);
  32.     while (r < qr) add(++r);
  33.     while (r > qr) del(r--);
  34.     return quantity;
  35. }
  36. void dnc(int j, int l, int r, int optl, int optr)
  37. {
  38.     if (l > r) return ;
  39.     int m = l + r >> 1;
  40.     ii best = {INF, -1};
  41.  
  42.     for (int z = optl; z <= min(m, optr); z++)
  43.         best = min(best, {dp[z - 1][j - 1] + cost(z, m), z});
  44.  
  45.     dp[m][j] = best.fi;
  46.     dnc(j, l, m - 1, optl, best.se);
  47.     dnc(j, m + 1, r, best.se, optr);
  48. }
  49.  
  50. int main()
  51. {
  52.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  53.     if (fopen("YET.INP", "r"))
  54.     {
  55.         freopen("YET.INP", "r", stdin);
  56.         freopen("YET.OUT", "w", stdout);
  57.     }
  58.  
  59.     cin >> n >> k;
  60.     for (int i = 1; i <= n; i++)
  61.         cin >> a[i];
  62.     for (int i = 0; i <= n; i++)
  63.         for (int j = 0; j <= k; j++)
  64.             dp[i][j] = INF;
  65.     dp[0][0] = 0;
  66. //    for (int j = 1; j <= k; j++)
  67. //        for (int i = 1; i <= n; i++)
  68. //            for (int z = 1; z <= i; z++)
  69. //                dp[i][j] = min(dp[i][j], dp[z - 1][j - 1] + cost(z, i));
  70. //
  71.     for (int j = 1; j <= k; j++)
  72.         dnc(j, 1, n, 1, n);
  73. //    for (int j = 1; j <= k; j++)
  74. //    {
  75. //        for (int i = 1; i <= n; i++)
  76. //            cout << dp[i][j] << ' ';
  77. //        el;
  78. //    }
  79.     cout << dp[n][k];
  80. }
  81.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/o0rU2z
language:
C++14 (gcc 8.3)
created:
215 days ago
visibility:
secret

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!