#include <cstdlib> #include <bitset> #include <functional> #include <utility> #include <chrono> #include <tuple> #include <new> #include <memory> #include <climits> #include <cfloat> #include <cinttypes> #include <exception> #include <string> #include <array> #include <vector> #include <deque> #include <list> #include <forward_list> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <valarray> #include <ios> #include <istream> #include <ostream> #include <iostream> #include <fstream> #include <streambuf> #include <cstdio> #include <thread> // #include <bits/stdc++.h> using namespace std; int n, czas_przejazdu, maksymalne_do_ominiecia; int laczna_l_spotkan; int tab[8005]; // 1 biuro 2 zdalne 3 brak int prefiksowe[8005][4]; int koniec, poczatek; int wyn = -1; char znak; int policz(int w_pracy, int w_domu, int dl_w_domu) { int tymcz_potrzebne = laczna_l_spotkan - maksymalne_do_ominiecia - w_pracy; if (tymcz_potrzebne > 0) { w_domu -= tymcz_potrzebne; dl_w_domu -= tymcz_potrzebne; } if (w_domu < 0) return -1; return dl_w_domu; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> maksymalne_do_ominiecia >> czas_przejazdu; for (int i = 1; i <= n; i++) { cin >> znak; if (znak == '1') tab[i] = 1; else if (znak == '2') tab[i] = 2; else tab[i] = 3; prefiksowe[i][1] = prefiksowe[i - 1][1]; prefiksowe[i][2] = prefiksowe[i - 1][2]; if (tab[i] == 1) { prefiksowe[i][1]++; laczna_l_spotkan++; } else if (tab[i] == 2) { prefiksowe[i][2]++; laczna_l_spotkan++; } } wyn = policz(0, prefiksowe[n][2], n); for (int i = czas_przejazdu + 1; i <= n - czas_przejazdu; i++) { for (int j = i; j <= n - czas_przejazdu; j++) { koniec = i - czas_przejazdu - 1; poczatek = j + czas_przejazdu + 1; wyn = max(wyn, policz(prefiksowe[j][1] - prefiksowe[i - 1][1] + prefiksowe[j][2] - prefiksowe[i - 1][2], prefiksowe[n][2] - prefiksowe[poczatek - 1][2] + prefiksowe[koniec][2], n - (j - i + 1 + 2 * czas_przejazdu))); } } cout << wyn; }
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 <cstdlib> #include <bitset> #include <functional> #include <utility> #include <chrono> #include <tuple> #include <new> #include <memory> #include <climits> #include <cfloat> #include <cinttypes> #include <exception> #include <string> #include <array> #include <vector> #include <deque> #include <list> #include <forward_list> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <valarray> #include <ios> #include <istream> #include <ostream> #include <iostream> #include <fstream> #include <streambuf> #include <cstdio> #include <thread> // #include <bits/stdc++.h> using namespace std; int n, czas_przejazdu, maksymalne_do_ominiecia; int laczna_l_spotkan; int tab[8005]; // 1 biuro 2 zdalne 3 brak int prefiksowe[8005][4]; int koniec, poczatek; int wyn = -1; char znak; int policz(int w_pracy, int w_domu, int dl_w_domu) { int tymcz_potrzebne = laczna_l_spotkan - maksymalne_do_ominiecia - w_pracy; if (tymcz_potrzebne > 0) { w_domu -= tymcz_potrzebne; dl_w_domu -= tymcz_potrzebne; } if (w_domu < 0) return -1; return dl_w_domu; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> maksymalne_do_ominiecia >> czas_przejazdu; for (int i = 1; i <= n; i++) { cin >> znak; if (znak == '1') tab[i] = 1; else if (znak == '2') tab[i] = 2; else tab[i] = 3; prefiksowe[i][1] = prefiksowe[i - 1][1]; prefiksowe[i][2] = prefiksowe[i - 1][2]; if (tab[i] == 1) { prefiksowe[i][1]++; laczna_l_spotkan++; } else if (tab[i] == 2) { prefiksowe[i][2]++; laczna_l_spotkan++; } } wyn = policz(0, prefiksowe[n][2], n); for (int i = czas_przejazdu + 1; i <= n - czas_przejazdu; i++) { for (int j = i; j <= n - czas_przejazdu; j++) { koniec = i - czas_przejazdu - 1; poczatek = j + czas_przejazdu + 1; wyn = max(wyn, policz(prefiksowe[j][1] - prefiksowe[i - 1][1] + prefiksowe[j][2] - prefiksowe[i - 1][2], prefiksowe[n][2] - prefiksowe[poczatek - 1][2] + prefiksowe[koniec][2], n - (j - i + 1 + 2 * czas_przejazdu))); } } cout << wyn; } |