#include <bits/stdc++.h> using namespace std; int pref1[8007]; int pref2[8007]; int pref3[8007]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, t; cin >> n >> k >> t; string s; cin >> s; for (int i = 1; i <= n; i++) { pref1[i] = pref1[i - 1]; pref2[i] = pref2[i - 1]; pref3[i] = pref3[i - 1]; if (s[i - 1] == '1') { pref1[i]++; } if (s[i - 1] == '2') { pref2[i]++; } if (s[i - 1] == '3') { pref3[i]++; } } int odp = -1; if (k >= pref1[n]) { odp = pref3[n] + pref1[n] + min(pref2[n], k - pref1[n]); } for (int startp = 0; startp <= n - 2 * t; startp++) { for (int koniecb = startp + 2 * t - 1; koniecb < n; koniecb++) { if (k - (pref1[startp + t] - pref1[startp]) - (pref2[startp + t] - pref2[startp]) - (pref1[koniecb + 1] - pref1[koniecb - t + 1]) - (pref2[koniecb + 1] - pref2[koniecb - t + 1]) >= pref1[startp] + (pref1[n] - pref1[koniecb + 1])) { odp = max(odp, pref3[startp] + (pref3[n] - pref3[koniecb + 1]) + pref1[startp] + (pref1[n] - pref1[koniecb + 1]) + min(pref2[startp] + (pref2[n] - pref2[koniecb + 1]), k - (pref1[startp + t] - pref1[startp]) - (pref2[startp + t] - pref2[startp]) - (pref1[koniecb + 1] - pref1[koniecb - t + 1]) - (pref2[koniecb + 1] - pref2[koniecb - t + 1]) - pref1[startp] - (pref1[n] - pref1[koniecb + 1]))); } } } cout << odp << endl; return 0; }
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <bits/stdc++.h> using namespace std; int pref1[8007]; int pref2[8007]; int pref3[8007]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, t; cin >> n >> k >> t; string s; cin >> s; for (int i = 1; i <= n; i++) { pref1[i] = pref1[i - 1]; pref2[i] = pref2[i - 1]; pref3[i] = pref3[i - 1]; if (s[i - 1] == '1') { pref1[i]++; } if (s[i - 1] == '2') { pref2[i]++; } if (s[i - 1] == '3') { pref3[i]++; } } int odp = -1; if (k >= pref1[n]) { odp = pref3[n] + pref1[n] + min(pref2[n], k - pref1[n]); } for (int startp = 0; startp <= n - 2 * t; startp++) { for (int koniecb = startp + 2 * t - 1; koniecb < n; koniecb++) { if (k - (pref1[startp + t] - pref1[startp]) - (pref2[startp + t] - pref2[startp]) - (pref1[koniecb + 1] - pref1[koniecb - t + 1]) - (pref2[koniecb + 1] - pref2[koniecb - t + 1]) >= pref1[startp] + (pref1[n] - pref1[koniecb + 1])) { odp = max(odp, pref3[startp] + (pref3[n] - pref3[koniecb + 1]) + pref1[startp] + (pref1[n] - pref1[koniecb + 1]) + min(pref2[startp] + (pref2[n] - pref2[koniecb + 1]), k - (pref1[startp + t] - pref1[startp]) - (pref2[startp + t] - pref2[startp]) - (pref1[koniecb + 1] - pref1[koniecb - t + 1]) - (pref2[koniecb + 1] - pref2[koniecb - t + 1]) - pref1[startp] - (pref1[n] - pref1[koniecb + 1]))); } } } cout << odp << endl; return 0; } |