fork download
copy 
  1. // #pragma GCC optimize("O3,unroll-loops")
  2. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // __builtin_popcount
  6. // __builtin_ctz
  7. // #define int long long
  8. #define pii pair<int, int>
  9. #define duoble long double
  10. #define endl '\n'
  11. #define fi first
  12. #define se second
  13. #define mapa make_pair
  14. #define pushb push_back
  15. #define pushf push_front
  16. #define popb pop_back
  17. #define popf pop_front
  18. #define o_ ordered_
  19. #define ins insert
  20. #define era erase
  21. #define pqueue priority_queue
  22. #define minele min_element
  23. #define maxele max_element
  24. #define lb lower_bound // >=
  25. #define ub upper_bound // >
  26. #define debug cout << "NO ERROR", exit(0)
  27. #define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28. #define MASK(i) (1LL << (i))
  29. #define BIT(x, i) (((x) >> (i)) & 1)
  30. #define ALL(v) v.begin(), v.end()
  31. #define SZ(v) (int)v.size()
  32. #define sqr(x) ((x) * (x))
  33.  
  34. template<class X, class Y>
  35.     bool minimize(X &x, const Y &y) {
  36.         if (x > y) {
  37.             x = y;
  38.             return true;
  39.         }
  40.         return false;
  41.     }
  42. template<class X, class Y>
  43.     bool maximize(X &x, const Y &y) {
  44.         if (x < y) {
  45.             x = y;
  46.             return true;
  47.         }
  48.         return false;
  49.     }
  50.  
  51. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  52.  
  53. int Rand(const int &l, const int &r) {
  54.     assert(l <= r);
  55.     int sz = (r - l + 1);
  56.     return l + rd() % sz;
  57. }
  58.  
  59.  
  60. const int MOD = 1e9 + 7; //998244353;
  61. const int LOG = 18;
  62. const int INF = 1e9 + 7;
  63. const int d4x[4] = {-1, 1, 0, 0};
  64. const int d4y[4] = {0, 0, 1, -1};
  65. const char c4[4] = {'U', 'D', 'R', 'L'};
  66. const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  67. const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  68.  
  69.  
  70.  
  71.  
  72. // #define LENGTH 1000005
  73. // #define NMOD 2
  74. // #define BASE 256
  75. // const int HashMod[] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277};
  76.  
  77. // #include <ext/pb_ds/assoc_container.hpp>
  78. // #include <ext/pb_ds/tree_policy.hpp>
  79. // using namespace __gnu_pbds;
  80. // #define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
  81. // *(s.find_by_order(2)) : 3rd element in the set i.e. 6
  82. // s.order_of_key(25) : Count of elements strictly smaller than 25 is 4
  83.  
  84.  
  85.  
  86.  
  87. /* Listen music of IU before enjoy my code */
  88.  
  89. const int LimN = 5e3 + 5;
  90.  
  91. int n, k, a[LimN], f[LimN][LimN], pref[LimN], pre[LimN];
  92.  
  93. void compress() {
  94.     vector<int> comp;
  95.     for (int i = 1; i <= n; i++) {
  96.         comp.pushb(a[i]);
  97.     }
  98.     sort(ALL(comp));
  99.     comp.resize(unique(ALL(comp)) - comp.begin());
  100.     for (int i = 1; i <= n; i++) {
  101.         a[i] = lb(ALL(comp), a[i]) - comp.begin() + 1;
  102.     }
  103. }
  104.  
  105.  
  106. void solve() {
  107.  
  108.     cin >> n >> k;
  109.     for (int i = 1; i <= n; i++) cin >> a[i];
  110.  
  111.     compress();
  112.     memset(f, 0x3f, sizeof f);
  113.     memset(pref, 0x3f, sizeof pref);
  114.     memset(pre, -1, sizeof pre);
  115.  
  116.     // for (int i = 1; i <= n; i++) cout << a[i] << " " << pre[a[i]] << endl;
  117.  
  118.     pref[0] = 0;
  119.     int ans = INF;
  120.     for (int i = 1; i <= n; i++) {
  121.         for (int j = 1; j <= k + 1; j++) {
  122.             f[i][j] = pref[j - 1] + i - 1;
  123.             if (pre[a[i]] != -1) minimize(f[i][j], f[pre[a[i]]][j] + (i - pre[a[i]] - 1));
  124.         }
  125.         for (int j = 1; j <= k + 1; j++) {
  126.             minimize(pref[j], f[i][j] - i);
  127.             minimize(ans, f[i][j] + n - i);
  128.         }
  129.         pre[a[i]] = i;
  130.     }
  131.     cout << ans << endl;
  132.  
  133.  
  134.  
  135.  
  136. }
  137.  
  138.  
  139. /* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students Da Nang */
  140.  
  141.  
  142.  
  143. signed main() {
  144.  
  145.     #ifndef ONLINE_JUDGE
  146.     freopen("ab.inp", "r", stdin);
  147.     freopen("ab.out", "w", stdout);
  148.     #else
  149.     // freopen("task.inp", "r", stdin);
  150.     // freopen("task.out", "w", stdout);
  151.     #endif
  152.     FAST;
  153.     bool TestCase = 0;
  154.     int NumTest = 1;
  155.     cin >> NumTest;
  156.     for (int i = 1; i <= NumTest; i++) {
  157.         if (TestCase) cout << "Case" << " " << i << ": ";
  158.         solve();
  159.     }
  160.  
  161. }
  162.  
Success #stdin #stdout 0.02s 101440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/xC3WeL
language:
C++14 (gcc 8.3)
created:
2 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!