//Karol Dziekan #include <bits/stdc++.h> using namespace std; #define endl '\n' #define LL long long int int main(){ std::ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); int n; int k; int t; int ilosc_spotkan_ogolem = 0; int wynik = -1; cin >> n >> k >> t; vector<int> pref_wolne(n + 1,0); vector<int> pref_zdalne(n + 1,0); vector<int> pref_praca(n + 1,0); for (int i = 1; i <= n; i++){ char sytuacja; cin >> sytuacja; if (sytuacja == '1'){ pref_praca[i] = 1; ilosc_spotkan_ogolem++; } if (sytuacja == '2'){ pref_zdalne[i] = 1; ilosc_spotkan_ogolem++; } if (sytuacja == '3'){ pref_wolne[i] = 1; } pref_praca[i] += pref_praca[i-1]; pref_zdalne[i] += pref_zdalne[i-1]; pref_wolne[i] += pref_wolne[i-1]; } //Liczenie bez podrozy do pracy int czas_wolny = pref_wolne[n] + pref_praca[n]; if (pref_praca[n] <= k){ czas_wolny += min(k - pref_praca[n], pref_zdalne[n]); wynik = czas_wolny; } //Liczenie z jedna podroza do pracy for (int i = 1; i <= n; i++){ for (int j = i; j <= n; j++){ if (j - i + 1 > 2 * t){ int opuszczone_spotkania = ilosc_spotkan_ogolem; int czas_wolny = pref_wolne[i-1] + (pref_wolne[n] - pref_wolne[j]); int ilosc_spotkan_dom = pref_zdalne[i-1] + (pref_zdalne[n] - pref_zdalne[j]); int ilosc_spotkan_biuro = (pref_praca[j-t] - pref_praca[i+t-1]) + (pref_zdalne[j-t] - pref_zdalne[i+t-1]); opuszczone_spotkania -= ilosc_spotkan_biuro; if (opuszczone_spotkania > k){ int ile_brakuje_spotkan = opuszczone_spotkania - k; if (ile_brakuje_spotkan <= ilosc_spotkan_dom){ wynik = max(wynik, czas_wolny + ilosc_spotkan_dom - ile_brakuje_spotkan); } }else{ wynik = max(wynik, czas_wolny + ilosc_spotkan_dom); } } } } cout << wynik; 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 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 | //Karol Dziekan #include <bits/stdc++.h> using namespace std; #define endl '\n' #define LL long long int int main(){ std::ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); int n; int k; int t; int ilosc_spotkan_ogolem = 0; int wynik = -1; cin >> n >> k >> t; vector<int> pref_wolne(n + 1,0); vector<int> pref_zdalne(n + 1,0); vector<int> pref_praca(n + 1,0); for (int i = 1; i <= n; i++){ char sytuacja; cin >> sytuacja; if (sytuacja == '1'){ pref_praca[i] = 1; ilosc_spotkan_ogolem++; } if (sytuacja == '2'){ pref_zdalne[i] = 1; ilosc_spotkan_ogolem++; } if (sytuacja == '3'){ pref_wolne[i] = 1; } pref_praca[i] += pref_praca[i-1]; pref_zdalne[i] += pref_zdalne[i-1]; pref_wolne[i] += pref_wolne[i-1]; } //Liczenie bez podrozy do pracy int czas_wolny = pref_wolne[n] + pref_praca[n]; if (pref_praca[n] <= k){ czas_wolny += min(k - pref_praca[n], pref_zdalne[n]); wynik = czas_wolny; } //Liczenie z jedna podroza do pracy for (int i = 1; i <= n; i++){ for (int j = i; j <= n; j++){ if (j - i + 1 > 2 * t){ int opuszczone_spotkania = ilosc_spotkan_ogolem; int czas_wolny = pref_wolne[i-1] + (pref_wolne[n] - pref_wolne[j]); int ilosc_spotkan_dom = pref_zdalne[i-1] + (pref_zdalne[n] - pref_zdalne[j]); int ilosc_spotkan_biuro = (pref_praca[j-t] - pref_praca[i+t-1]) + (pref_zdalne[j-t] - pref_zdalne[i+t-1]); opuszczone_spotkania -= ilosc_spotkan_biuro; if (opuszczone_spotkania > k){ int ile_brakuje_spotkan = opuszczone_spotkania - k; if (ile_brakuje_spotkan <= ilosc_spotkan_dom){ wynik = max(wynik, czas_wolny + ilosc_spotkan_dom - ile_brakuje_spotkan); } }else{ wynik = max(wynik, czas_wolny + ilosc_spotkan_dom); } } } } cout << wynik; return 0; } |