#include <bits/stdc++.h> #define ll long long #define range(i, n) for (int i = 0; i < n; i++) using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k, t; cin >> n >> k >> t; string s; cin >> s; int lastLeaveWork = n - t; int best = -1; vector<int> zdalnes(n+1, 0), lokalnes(n+1, 0); range(i, n) { zdalnes[i+1] = zdalnes[i] + (s[i] == '2' ? 1 : 0); lokalnes[i+1] = lokalnes[i] + (s[i] == '1' ? 1 : 0); } k = max(zdalnes[n] + lokalnes[n] - k, 0); if (k <= zdalnes[n]) { cout << n - k << "\n"; return 0; } for (int a = t; a < lastLeaveWork; a++) for (int b = a + t; b <= n; b++) { int av_spot = 0; av_spot += zdalnes[a-t]; int spot_w_pracy = lokalnes[b-t] - lokalnes[a]; spot_w_pracy += zdalnes[b-t] - zdalnes[a]; av_spot += spot_w_pracy; av_spot += zdalnes[n] - zdalnes[b]; if (av_spot >= k) { int spot_w_domu = max(0, k - spot_w_pracy); best = max(best, n - b + a - t - spot_w_domu); break; } } cout << best << "\n"; }
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 | #include <bits/stdc++.h> #define ll long long #define range(i, n) for (int i = 0; i < n; i++) using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k, t; cin >> n >> k >> t; string s; cin >> s; int lastLeaveWork = n - t; int best = -1; vector<int> zdalnes(n+1, 0), lokalnes(n+1, 0); range(i, n) { zdalnes[i+1] = zdalnes[i] + (s[i] == '2' ? 1 : 0); lokalnes[i+1] = lokalnes[i] + (s[i] == '1' ? 1 : 0); } k = max(zdalnes[n] + lokalnes[n] - k, 0); if (k <= zdalnes[n]) { cout << n - k << "\n"; return 0; } for (int a = t; a < lastLeaveWork; a++) for (int b = a + t; b <= n; b++) { int av_spot = 0; av_spot += zdalnes[a-t]; int spot_w_pracy = lokalnes[b-t] - lokalnes[a]; spot_w_pracy += zdalnes[b-t] - zdalnes[a]; av_spot += spot_w_pracy; av_spot += zdalnes[n] - zdalnes[b]; if (av_spot >= k) { int spot_w_domu = max(0, k - spot_w_pracy); best = max(best, n - b + a - t - spot_w_domu); break; } } cout << best << "\n"; } |