#include <bits/stdc++.h> using namespace std; #define fwd(i, a, n) for (int i = (a); i < (n); i++) #define rep(i, n) fwd(i, 0, n) #define all(X) X.begin(), X.end() #define sz(X) int(size(X)) #define pb push_back #define eb emplace_back #define st first #define nd second using pii = pair<int, int>; using vi = vector<int>; using ll = long long; using ld = long double; #ifdef LOC auto SS = signal(6, [](int) { *(int *)0 = 0; }); # define DTP(x, y) \ auto operator<<(auto &o, auto a)->decltype(y, o) { \ o << "("; \ x; \ return o << ")"; \ } DTP(o << a.st << ", " << a.nd, a.nd); DTP(for (auto i : a) o << i << ", ", all(a)); void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; } # define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x) #else # define deb(...) 0 #endif struct PrefixSum { vi p; PrefixSum(int n) : p(n + 1) { } void put(int pos) { p[pos] = 1; } void build() { int sum = 0; rep(i, sz(p)) { int new_sum = sum + p[i]; p[i] = sum; sum = new_sum; } } // Exclusive [l, r) int get(int l, int r) { return p[r] - p[l]; } }; inline int calc_wolne(int biuro, int zdalne, int wolne, int trzeba) { trzeba -= biuro; trzeba = max(trzeba, 0); if (trzeba > zdalne) return -1; return wolne + zdalne - trzeba; } void sol() { int n, k, t; cin >> n >> k >> t; string s; cin >> s; PrefixSum biuro(n), zdalne(n), wolne(n); rep(i, n) { if (s[i] == '1') biuro.put(i); else if (s[i] == '2') zdalne.put(i); else wolne.put(i); } biuro.build(); zdalne.build(); wolne.build(); int ile_trzeba = biuro.get(0, n) + zdalne.get(0, n) - k; int max_wolne = calc_wolne(0, zdalne.get(0, n), n - zdalne.get(0, n), ile_trzeba); for (int a = 0; a + t <= n; a++) for (int b = a + t; b + t <= n; b++) { int ile_biuro = (b - (a + t)) - wolne.get(a + t, b); int ile_zdalne = zdalne.get(0, a) + zdalne.get(b + t, n); int ile_wolne = (a - 0) + (n - (b + t)) - ile_zdalne; max_wolne = max(max_wolne, calc_wolne(ile_biuro, ile_zdalne, ile_wolne, ile_trzeba)); } cout << max_wolne << '\n'; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(10); sol(); #ifdef LOCF cout.flush(); cerr << "- - - - - - - - -\n"; (void)!system( "grep VmPeak /proc/$PPID/status | sed s/....kB/\' MB\'/1 >&2"); // 4x.kB // ....kB #endif }
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #include <bits/stdc++.h> using namespace std; #define fwd(i, a, n) for (int i = (a); i < (n); i++) #define rep(i, n) fwd(i, 0, n) #define all(X) X.begin(), X.end() #define sz(X) int(size(X)) #define pb push_back #define eb emplace_back #define st first #define nd second using pii = pair<int, int>; using vi = vector<int>; using ll = long long; using ld = long double; #ifdef LOC auto SS = signal(6, [](int) { *(int *)0 = 0; }); # define DTP(x, y) \ auto operator<<(auto &o, auto a)->decltype(y, o) { \ o << "("; \ x; \ return o << ")"; \ } DTP(o << a.st << ", " << a.nd, a.nd); DTP(for (auto i : a) o << i << ", ", all(a)); void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; } # define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x) #else # define deb(...) 0 #endif struct PrefixSum { vi p; PrefixSum(int n) : p(n + 1) { } void put(int pos) { p[pos] = 1; } void build() { int sum = 0; rep(i, sz(p)) { int new_sum = sum + p[i]; p[i] = sum; sum = new_sum; } } // Exclusive [l, r) int get(int l, int r) { return p[r] - p[l]; } }; inline int calc_wolne(int biuro, int zdalne, int wolne, int trzeba) { trzeba -= biuro; trzeba = max(trzeba, 0); if (trzeba > zdalne) return -1; return wolne + zdalne - trzeba; } void sol() { int n, k, t; cin >> n >> k >> t; string s; cin >> s; PrefixSum biuro(n), zdalne(n), wolne(n); rep(i, n) { if (s[i] == '1') biuro.put(i); else if (s[i] == '2') zdalne.put(i); else wolne.put(i); } biuro.build(); zdalne.build(); wolne.build(); int ile_trzeba = biuro.get(0, n) + zdalne.get(0, n) - k; int max_wolne = calc_wolne(0, zdalne.get(0, n), n - zdalne.get(0, n), ile_trzeba); for (int a = 0; a + t <= n; a++) for (int b = a + t; b + t <= n; b++) { int ile_biuro = (b - (a + t)) - wolne.get(a + t, b); int ile_zdalne = zdalne.get(0, a) + zdalne.get(b + t, n); int ile_wolne = (a - 0) + (n - (b + t)) - ile_zdalne; max_wolne = max(max_wolne, calc_wolne(ile_biuro, ile_zdalne, ile_wolne, ile_trzeba)); } cout << max_wolne << '\n'; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(10); sol(); #ifdef LOCF cout.flush(); cerr << "- - - - - - - - -\n"; (void)!system( "grep VmPeak /proc/$PPID/status | sed s/....kB/\' MB\'/1 >&2"); // 4x.kB // ....kB #endif } |