fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define maxx 100005
  5. #define base 36
  6. #define MOD 1003472009
  7. #define x first
  8. #define y second
  9. long long n, m, k, a[maxx], s[4*maxx], start[maxx];
  10. vector<long long> f[maxx];
  11. long long dp[305][maxx];
  12. void update(int id, int x, int y, int u, long long v)
  13. {
  14.     if(x>u||y<u) return;
  15.     if(x==y&&x==u)
  16.     {
  17.         s[id]=max(s[id], v);
  18.         return;
  19.     }
  20.     int mid=(x+y)/2;
  21.     update(id*2, x, mid, u, v);
  22.     update(id*2+1, mid+1, y, u, v);
  23.     s[id]=max(s[id*2], s[id*2+1]);
  24. }
  25. long long get(int id, int x, int y, int u, int v)
  26. {
  27.     if(x>v||y<u) return -1e18;
  28.     if(x>=u&&y<=v) return s[id];
  29.     int mid=(x+y)/2;
  30.     return max(get(id*2, x, mid, u, v), get(id*2+1, mid+1, y, u, v));
  31. }
  32.  
  33. long long solve1()
  34. {
  35.     map<int, int> f;
  36.     int ans=0;
  37.     for(int i=1; i<=n; i++)
  38.     {
  39.         if(f[a[i]]==m)
  40.         {
  41.             f.clear();
  42.             ans++;
  43.         }
  44.         f[a[i]]++;
  45.     }
  46.     return ans+1;
  47. }
  48. long long solve2()
  49. {
  50.     for(int i=1; i<=n; i++)
  51.     {
  52.         f[a[i]].push_back(i);
  53.         int t=f[a[i]].size();
  54.         if(t>m)
  55.             update(1, 1, n, i, f[a[i]][t-m-1]+1);
  56.         start[i]=max((long long) 1, get(1, 1, n, 1, i));
  57.     }
  58.     memset(dp, 61, sizeof(dp));
  59.     dp[0][0]=0;
  60.     for(int i=0; i<=k; i++)
  61.     {
  62.         deque<int> ans;
  63.         for(int j=1; j<=n; j++)
  64.         {
  65.             if(i>0) dp[i][j]=min(dp[i][j], dp[i-1][j-1]);
  66.             while(!ans.empty()&&dp[i][ans.back()-1]>=dp[i][j-1]) ans.pop_back();
  67.             ans.push_back(j);
  68.             while(!ans.empty()&&ans.front()<start[j]) ans.pop_front();
  69.             dp[i][j]=min(dp[i][j], dp[i][ans.front()-1]+1);
  70.         }
  71.     }
  72.     long long kq=1e18;
  73.     for(int i=0; i<=k; i++)
  74.     {
  75.         kq=min(kq, dp[i][n]);
  76.     }
  77.     return kq;
  78. }
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0); cout.tie(0);
  83.     cin>>n>>m>>k;
  84.     for(int i=1; i<=n; i++) cin>>a[i];
  85.     if(k==0)
  86.     {
  87.         cout<<solve1();
  88.     }
  89.     else
  90.     {
  91.         cout<<solve2();
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 9748KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/UaF3Pm
language:
C++14 (gcc 8.3)
created:
3 hours 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!