Advertisement
fooker

P868F

Apr 3rd, 2024 (edited)
478
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. const ll nmax = 1e9+7;
  6. const ll nmax2 = 998244353;
  7.  
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. #include <ext/pb_ds/detail/standard_policies.hpp>
  11. using namespace __gnu_pbds;
  12. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  13. typedef tree<std::pair<ll, ll>, null_type, less<std::pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;
  14.  
  15. ll l_ = 0;
  16. ll r_ = 0;
  17. ll cost = 0;
  18. ll dp[21][100001];
  19.  
  20. std::vector<ll> cnt(100001);
  21. std::vector<ll> a(100001);
  22.  
  23. void prepare(ll n, ll k) {
  24.     for (ll i = 0; i <= k; i++){
  25.         for (ll j = 0; j <= n; j++) dp[i][j] = LLONG_MAX;
  26.     }
  27.  
  28.     for (ll i = 1; i <= k; i++) dp[i][0] = 0;
  29.     for (ll i = 0; i <= n; i++) dp[0][i] = 0;
  30.  
  31.     for (ll i = 1; i <= k; i++) {
  32.         for (ll j = 0; j < i; j++) dp[i][j] = 0;
  33.     }
  34.  
  35.     for (ll i = 1; i <= n; i++){
  36.         cnt[a[i]]++;
  37.         cost += (cnt[a[i]] - 1);
  38.         dp[1][i] = cost;
  39.     }
  40. }
  41.  
  42. void divide_and_conquer(ll j, ll l, ll r, ll L, ll R) {
  43.     ll mid = (l + r) >> 1;
  44.     if (l > r) return;
  45.  
  46.     while (r_ < mid) {
  47.         cnt[a[++r_]]++;
  48.         cost += (cnt[a[r_ - 1]] - 1);
  49.     }
  50.     while (r_ > mid) {
  51.         cnt[a[r_--]]--;
  52.         cost -= (cnt[a[r_ + 1]]);
  53.     }
  54.     while (l_ < L) {
  55.         cnt[a[l_++]]--;
  56.         cost -= (cnt[a[l_ - 1]]);
  57.     }
  58.     while (l_ > L) {
  59.         cnt[a[--l_]]++;
  60.         cost += (cnt[a[l_ + 1]] - 1);
  61.     }
  62.  
  63.     ll optimal = LLONG_MAX;
  64.     ll M = L;
  65.  
  66.     for (ll i = L; i <= R; i++) {
  67.         if (i > mid) break;
  68.  
  69.         while (l_ < i) {
  70.             cnt[a[l_++]]--;
  71.             cost -= (cnt[a[l_]]);
  72.         }
  73.  
  74.         dp[j][mid] = std::min(dp[j][mid], dp[j - 1][i - 1] + cost);
  75.  
  76.         if (optimal > dp[j][mid]) {
  77.             optimal = dp[j][mid];
  78.             M = i;
  79.         }
  80.     }
  81.    
  82.     divide_and_conquer(j, l, mid - 1, L, M);
  83.     divide_and_conquer(j, mid + 1, r, R, M);
  84. }
  85.  
  86. void solve() {
  87.     ll n, k;
  88.     std::cin >> n >> k;
  89.  
  90.     for (ll i = 1; i <= n; i++) std::cin >> a[i];
  91.  
  92.     prepare(n, k);
  93.  
  94.     for (ll i = 2; i <= k; i++) {
  95.         for (ll j = 0; j <= n; j++) cnt[j] = 0;
  96.        
  97.         cost = 0;
  98.         l_ = 0;
  99.         r_ = 0;
  100.  
  101.         divide_and_conquer(i, i, n, i, n);
  102.     }
  103.  
  104.     std::cout << dp[k][n] << '\n';
  105. }
  106.  
  107. int main(){
  108.     std::ios_base::sync_with_stdio(false);
  109.     std::cin.tie(0);
  110.     std::cout.tie(0);
  111.  
  112.     int t = 1;
  113.     // std::cin >> t;
  114.     while(t--) {
  115.         solve();
  116.     }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement