fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define MOD 1000000007
  9. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  10. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define ii pair<ll,ll>
  13. #define iii pair<ll,pair<ll,int>>
  14. //const int MOD = 998244353;
  15. const int MAXN = 1e5 + 7;
  16. int a[MAXN],dd[MAXN];
  17. int main(){
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(0); cout.tie(0);
  20.     //freopen("COMNUM.inp","r",stdin);
  21.     //freopen("COMNUM.out","w",stdout);
  22.     int n,m,k;cin >> n >> m >> k;
  23.     FOR(i,1,n)cin >> a[i];
  24.     if (k > n)return cout << 0,0;
  25.     vector<vector<int>> dp(n + 7,vector<int>(k + 7));
  26.     FOR(i,1,n){
  27.         FOR(j,0,k)dp[i][j] = 1e9;
  28.         int w = 0;
  29.         FOD(j,1,i){
  30.             dd[a[j]]++;
  31.             if (dd[a[j]] > m){
  32.                 w++;
  33.                 dd[a[j]]--;
  34.             } 
  35.             if (w > k){
  36.                FOR(x,j,i)dd[a[x]] = 0;
  37.                break;
  38.             }
  39.             FOR(x,w,k)dp[i][x] = min(dp[i][x],dp[j - 1][x - w] + 1);
  40.             if (j == 1)FOR(x,j,i)dd[a[x]] = 0;
  41.         }
  42.     }
  43.     cout << dp[n][k];
  44.     return 0^0;
  45. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/K8RsgA
language:
C++ (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!