fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 5;
  6. int a[N];
  7. int n,k,x;
  8. int cnt[10][N];
  9.  
  10. int check(int l, int r) { /// O(10)
  11.     /// 1. Dem trong doan l,r co bao nhieu so khac nhau
  12.     int khacnhau = 0;
  13.     vector<pair<int, int>> candidates;
  14.     int tot = 0;
  15.     for (int i = 1; i <= 9; i++) {
  16.         if (cnt[i][r] - cnt[i][l-1] > 0)        {
  17.             khacnhau++;
  18.             int sl  = cnt[i][r] - cnt[i][l-1];
  19.             tot += sl;
  20.             candidates.push_back({sl,i});
  21.         }
  22.     }
  23.     if (khacnhau <= k)      return -1;
  24.     sort(candidates.begin(), candidates.end(), greater<pair<int,int>>());
  25.     int cur = 0; /// Tong cnt cua k so co cnt lon nhat
  26.     for (int i = 0; i < k; i++) {
  27.         cur += candidates[i].first;
  28.     }
  29.     int remain = tot - cur;
  30.     return remain;
  31. }
  32.  
  33. int main() {
  34.     /// freopen("DENLONG.INP","r",stdin);
  35.     // freopen("DENLONG.OUT","w",stdout);
  36.     ios::sync_with_stdio(0),    cin.tie(0), cout.tie(0);
  37.  
  38.     cin >> n >> k >> x;
  39.     for (int i = 1; i <= n; i++)    cin >> a[i];
  40.  
  41.     for (int i = 1; i <= n; i++) {
  42.         for (int c = 1; c <= 9; c++) {
  43.             cnt[c][i] = cnt[c][i-1] + (a[i] == c);
  44.         }
  45.     }
  46.  
  47.     int ans = -1;
  48.     int l=1,r=1;
  49.     while (l <= r) {
  50.         int cur_amt = check(l,r);
  51.         if (cur_amt == -1 || cur_amt <= x)      {
  52.             ans = max(ans,r-l+1);
  53.             if (r + 1 <= n)     r++;
  54.             else l++;
  55.         }
  56.         else l++;
  57.     }
  58.     cout << ans;
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/KH9tzJ
language:
C++14 (gcc 8.3)
created:
7 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!