fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define li pair<long long , int>
  10. #define db double
  11. #define onBit(mask , i) (mask | (1 << i))
  12. #define offBit(mask , i) (mask & (~(1 << i)))
  13.  
  14. const long long MOD = 1e9 + 7;
  15. const long long INF = 1e14;
  16. const int N = 8e3 + 7;
  17. int n , k , t;
  18. string s;
  19. int pre_1[N] , pre_2[N] , pre_3[N] , suf_1[N] , suf_2[N] , suf_3[N];
  20.  
  21. void inp(){
  22.     cin >> n >> k >> t;
  23.     cin >> s;
  24.     s = "L" + s;
  25.     for (int i = 1 ; i <= n ; ++i){
  26.         if (s[i] == '3') pre_3[i] = pre_3[i - 1] + 1;
  27.         else pre_3[i] = pre_3[i - 1];
  28.         if (s[i] == '1') pre_1[i] = pre_1[i - 1] + 1;
  29.         else pre_1[i] = pre_1[i - 1];
  30.         if (s[i] == '2') pre_2[i] = pre_2[i - 1] + 1;
  31.         else pre_2[i] = pre_2[i - 1];
  32.     }
  33.     for (int i = n ; i >= 1 ; --i){
  34.         if (s[i] == '3') suf_3[i] = suf_3[i + 1] + 1;
  35.         else suf_3[i] = suf_3[i + 1];
  36.         if (s[i] == '1') suf_1[i] = suf_1[i + 1] + 1;
  37.         else suf_1[i] = suf_1[i + 1];
  38.         if (s[i] == '2') suf_2[i] = suf_2[i + 1] + 1;
  39.         else suf_2[i] = suf_2[i + 1];
  40.     }
  41. }
  42.  
  43. int check(int i , int j){
  44.     int cnt = 0;
  45.     cnt += pre_2[i + t - 1] - pre_2[i - 1];
  46.     cnt += pre_1[i + t - 1] - pre_1[i - 1];
  47.     cnt += suf_2[j - t + 1] - suf_2[j + 1];
  48.     cnt += suf_1[j - t + 1] - suf_1[j + 1];
  49.     cnt += pre_1[i - 1];
  50.     cnt += suf_1[j + 1];
  51.     return cnt;
  52. }
  53.  
  54. void solve(){
  55.     if (pre_1[n] <= k){
  56.         k -= pre_1[n];
  57.         if (pre_2[n] <= k){
  58.             cout << n;
  59.             return;
  60.         }
  61.         cout << n - pre_2[n] + k;
  62.         return;
  63.     }
  64.     int res = -1;
  65.     for (int i = 1 ; i <= n - 2 * t ; ++i){
  66.         for (int j = i + 2 * t ; j <= n ; ++j){
  67.             int tmp = check(i , j);
  68.             if (tmp > k) continue;
  69.  
  70.             int add = 0;
  71.             if (tmp < k) add = min(k - tmp , pre_2[i - 1] + suf_2[j + 1]);
  72.             res = max(res , pre_3[i - 1] + suf_3[j + 1] + pre_1[i - 1] + suf_1[j + 1] + add);
  73. //            cout  << i << " " << j << " " << tmp << " " << pre_3[i - 1] + suf_3[j + 1] + pre_1[i - 1] + suf_1[j + 1] + add << '\n';
  74.         }
  75.     }
  76.     cout << res;
  77. }
  78.  
  79. int main(){
  80.     // freopen("xhmax.inp" , "r" , stdin);
  81.     // freopen("xhmax.out" , "w" , stdout);
  82.     faster;
  83.     inp();
  84.     solve();
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OdH2F9
language:
C++14 (gcc 8.3)
created:
6 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!