#include <bits/stdc++.h> using namespace std; int n, k, t; char s[8010]; int pref[4][8010], suf[4][8010]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t; cin >> s; for (int i = n; i > 0; i--) s[i] = s[i-1]; int res = -1; for (int i = 1; i <= n; i++) { for (int j = 1; j < 4; j++) pref[j][i] = pref[j][i-1]; pref[s[i]-'0'][i]++; } for (int i = n; i > 0; i--) { for (int j = 1; j < 4; j++) suf[j][i] = suf[j][i+1]; suf[s[i]-'0'][i]++; } if (pref[1][n] <= k) { res = min(n, pref[3][n]+k); } for (int i = t+1; i <= n-t; i++) { for (int j = i; j <= n-t; j++) { int ileMinietych = pref[1][i-1]+pref[2][i-1]-pref[2][i-1-t]+suf[1][j+1]+suf[2][j+1]-suf[2][j+1+t]; int droga = pref[1][i-1]-pref[1][i-1-t]+pref[2][i-1]-pref[2][i-1-t]+suf[1][j+1]-suf[1][j+1+t]+suf[2][j+1]-suf[2][j+1+t]; if (ileMinietych > k) continue; //cout << ileMinietych << ' ' << i << ' ' << j << '\n'; res = max(res, min(pref[3][i-1-t]+suf[3][j+1+t] + k-droga,n-t*2)); } } cout << res; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <bits/stdc++.h> using namespace std; int n, k, t; char s[8010]; int pref[4][8010], suf[4][8010]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t; cin >> s; for (int i = n; i > 0; i--) s[i] = s[i-1]; int res = -1; for (int i = 1; i <= n; i++) { for (int j = 1; j < 4; j++) pref[j][i] = pref[j][i-1]; pref[s[i]-'0'][i]++; } for (int i = n; i > 0; i--) { for (int j = 1; j < 4; j++) suf[j][i] = suf[j][i+1]; suf[s[i]-'0'][i]++; } if (pref[1][n] <= k) { res = min(n, pref[3][n]+k); } for (int i = t+1; i <= n-t; i++) { for (int j = i; j <= n-t; j++) { int ileMinietych = pref[1][i-1]+pref[2][i-1]-pref[2][i-1-t]+suf[1][j+1]+suf[2][j+1]-suf[2][j+1+t]; int droga = pref[1][i-1]-pref[1][i-1-t]+pref[2][i-1]-pref[2][i-1-t]+suf[1][j+1]-suf[1][j+1+t]+suf[2][j+1]-suf[2][j+1+t]; if (ileMinietych > k) continue; //cout << ileMinietych << ' ' << i << ' ' << j << '\n'; res = max(res, min(pref[3][i-1-t]+suf[3][j+1+t] + k-droga,n-t*2)); } } cout << res; } |