#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int main() { int kluski, kotlet, traktor; cin >> kluski >> kotlet >> traktor; string obowiazki; cin >> obowiazki; vector<int> cebula(kluski + 1, 0); vector<int> ziemniak(kluski + 1, 0); vector<int> ogorek(kluski + 1, 0); for (int schab = 0; schab < kluski; ++schab) { cebula[schab + 1] = cebula[schab] + (obowiazki[schab] == '1'); ziemniak[schab + 1] = ziemniak[schab] + (obowiazki[schab] == '2'); ogorek[schab + 1] = ogorek[schab] + (obowiazki[schab] == '3'); } int max_robotka = -1; int suma_cebula = cebula[kluski]; if (suma_cebula <= kotlet) { int reszta_kotleta = kotlet - suma_cebula; int suma_ziemniak = ziemniak[kluski]; int pominiete_ziemniaki = min(suma_ziemniak, reszta_kotleta); int robotka = suma_cebula + ogorek[kluski] + pominiete_ziemniaki; max_robotka = max(max_robotka, robotka); } for (int kapusta = 0; kapusta <= kluski - traktor; ++kapusta) { for (int burak = kapusta + traktor; burak + traktor <= kluski; ++burak) { int wyjazd_pocz = kapusta; int wyjazd_kon = kapusta + traktor; int powrot_pocz = burak; int powrot_kon = burak + traktor; int zgubione_droga = (cebula[wyjazd_kon] - cebula[wyjazd_pocz]) + (ziemniak[wyjazd_kon] - ziemniak[wyjazd_pocz]); int zgubione_powrot = (cebula[powrot_kon] - cebula[powrot_pocz]) + (ziemniak[powrot_kon] - ziemniak[powrot_pocz]); int dom_cebula_przed = cebula[kapusta]; int dom_cebula_po = cebula[kluski] - cebula[powrot_kon]; int suma_strat = zgubione_droga + zgubione_powrot + dom_cebula_przed + dom_cebula_po; if (suma_strat > kotlet) continue; int reszta_kotleta = kotlet - suma_strat; int dom_ziemniak_przed = ziemniak[kapusta]; int dom_ziemniak_po = ziemniak[kluski] - ziemniak[powrot_kon]; int suma_ziemniak = dom_ziemniak_przed + dom_ziemniak_po; int pominiete_ziemniaki = min(suma_ziemniak, reszta_kotleta); int dom_ogorek_przed = ogorek[kapusta]; int dom_ogorek_po = ogorek[kluski] - ogorek[powrot_kon]; int robotka = dom_cebula_przed + dom_cebula_po + dom_ogorek_przed + dom_ogorek_po + pominiete_ziemniaki; max_robotka = max(max_robotka, robotka); } } cout << (max_robotka == -1 ? -1 : max_robotka) << 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int main() { int kluski, kotlet, traktor; cin >> kluski >> kotlet >> traktor; string obowiazki; cin >> obowiazki; vector<int> cebula(kluski + 1, 0); vector<int> ziemniak(kluski + 1, 0); vector<int> ogorek(kluski + 1, 0); for (int schab = 0; schab < kluski; ++schab) { cebula[schab + 1] = cebula[schab] + (obowiazki[schab] == '1'); ziemniak[schab + 1] = ziemniak[schab] + (obowiazki[schab] == '2'); ogorek[schab + 1] = ogorek[schab] + (obowiazki[schab] == '3'); } int max_robotka = -1; int suma_cebula = cebula[kluski]; if (suma_cebula <= kotlet) { int reszta_kotleta = kotlet - suma_cebula; int suma_ziemniak = ziemniak[kluski]; int pominiete_ziemniaki = min(suma_ziemniak, reszta_kotleta); int robotka = suma_cebula + ogorek[kluski] + pominiete_ziemniaki; max_robotka = max(max_robotka, robotka); } for (int kapusta = 0; kapusta <= kluski - traktor; ++kapusta) { for (int burak = kapusta + traktor; burak + traktor <= kluski; ++burak) { int wyjazd_pocz = kapusta; int wyjazd_kon = kapusta + traktor; int powrot_pocz = burak; int powrot_kon = burak + traktor; int zgubione_droga = (cebula[wyjazd_kon] - cebula[wyjazd_pocz]) + (ziemniak[wyjazd_kon] - ziemniak[wyjazd_pocz]); int zgubione_powrot = (cebula[powrot_kon] - cebula[powrot_pocz]) + (ziemniak[powrot_kon] - ziemniak[powrot_pocz]); int dom_cebula_przed = cebula[kapusta]; int dom_cebula_po = cebula[kluski] - cebula[powrot_kon]; int suma_strat = zgubione_droga + zgubione_powrot + dom_cebula_przed + dom_cebula_po; if (suma_strat > kotlet) continue; int reszta_kotleta = kotlet - suma_strat; int dom_ziemniak_przed = ziemniak[kapusta]; int dom_ziemniak_po = ziemniak[kluski] - ziemniak[powrot_kon]; int suma_ziemniak = dom_ziemniak_przed + dom_ziemniak_po; int pominiete_ziemniaki = min(suma_ziemniak, reszta_kotleta); int dom_ogorek_przed = ogorek[kapusta]; int dom_ogorek_po = ogorek[kluski] - ogorek[powrot_kon]; int robotka = dom_cebula_przed + dom_cebula_po + dom_ogorek_przed + dom_ogorek_po + pominiete_ziemniaki; max_robotka = max(max_robotka, robotka); } } cout << (max_robotka == -1 ? -1 : max_robotka) << endl; return 0; } |