#include<bits/stdc++.h> using namespace std; const int maxn=8009; int wolne[maxn], zdalne[maxn], biuro[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, t; cin >> n >> k >> t; string s; cin >> s; for(int i=1; i<=n; i++) { zdalne[i]=zdalne[i-1]; biuro[i]=biuro[i-1]; wolne[i]=wolne[i-1]; if(s[i-1]=='2') { zdalne[i]++; } else if(s[i-1]=='1') { biuro[i]++; } else { wolne[i]++; } } int wyn=-1; int ile_opuszcza, teraz, ile_zdalnych, ile_wolnych, ile_biuro; for(int i=1; i<=n; i++) { //wyjazd z domu i-tego dnia for(int j=i+t+1; j<=n; j++) { if(j+t-1>n) { break; } //od 1 do i-1 dom //od i do i+t-1 jedzie //od i+t do j-1 praca //od j do j+t-1 jedzie //od j+t do n dom ile_opuszcza=0; ile_opuszcza+=biuro[i-1]; ile_opuszcza+=biuro[n]-biuro[j+t-1]; ile_opuszcza+=biuro[i+t-1]-biuro[i-1]; ile_opuszcza+=zdalne[i+t-1]-zdalne[i-1]; ile_opuszcza+=biuro[j+t-1]-biuro[j-1]; ile_opuszcza+=zdalne[j+t-1]-zdalne[j-1]; if(ile_opuszcza>k) { continue; } teraz=i-1 + n-(j+t-1); ile_zdalnych=zdalne[i-1] + zdalne[n]-zdalne[j+t-1]; ile_wolnych=wolne[i-1] + wolne[n]-wolne[j+t-1]; ile_biuro=biuro[i-1]+biuro[n]-biuro[j+t-1]; if(k-ile_opuszcza>=ile_zdalnych) { wyn=max(wyn, ile_wolnych+ile_zdalnych+ile_biuro); } else { wyn=max(wyn, ile_wolnych+k-ile_opuszcza+ile_biuro); } } } ile_opuszcza=biuro[n]; if(ile_opuszcza<=k) { ile_zdalnych=zdalne[n]; ile_wolnych=wolne[n]; ile_biuro=biuro[n]; if(k-ile_opuszcza>=ile_zdalnych) { wyn=max(wyn, ile_wolnych+ile_zdalnych+ile_biuro); } else { wyn=max(wyn, ile_wolnych+k-ile_opuszcza+ile_biuro); } } cout << wyn << endl; }
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 | #include<bits/stdc++.h> using namespace std; const int maxn=8009; int wolne[maxn], zdalne[maxn], biuro[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, t; cin >> n >> k >> t; string s; cin >> s; for(int i=1; i<=n; i++) { zdalne[i]=zdalne[i-1]; biuro[i]=biuro[i-1]; wolne[i]=wolne[i-1]; if(s[i-1]=='2') { zdalne[i]++; } else if(s[i-1]=='1') { biuro[i]++; } else { wolne[i]++; } } int wyn=-1; int ile_opuszcza, teraz, ile_zdalnych, ile_wolnych, ile_biuro; for(int i=1; i<=n; i++) { //wyjazd z domu i-tego dnia for(int j=i+t+1; j<=n; j++) { if(j+t-1>n) { break; } //od 1 do i-1 dom //od i do i+t-1 jedzie //od i+t do j-1 praca //od j do j+t-1 jedzie //od j+t do n dom ile_opuszcza=0; ile_opuszcza+=biuro[i-1]; ile_opuszcza+=biuro[n]-biuro[j+t-1]; ile_opuszcza+=biuro[i+t-1]-biuro[i-1]; ile_opuszcza+=zdalne[i+t-1]-zdalne[i-1]; ile_opuszcza+=biuro[j+t-1]-biuro[j-1]; ile_opuszcza+=zdalne[j+t-1]-zdalne[j-1]; if(ile_opuszcza>k) { continue; } teraz=i-1 + n-(j+t-1); ile_zdalnych=zdalne[i-1] + zdalne[n]-zdalne[j+t-1]; ile_wolnych=wolne[i-1] + wolne[n]-wolne[j+t-1]; ile_biuro=biuro[i-1]+biuro[n]-biuro[j+t-1]; if(k-ile_opuszcza>=ile_zdalnych) { wyn=max(wyn, ile_wolnych+ile_zdalnych+ile_biuro); } else { wyn=max(wyn, ile_wolnych+k-ile_opuszcza+ile_biuro); } } } ile_opuszcza=biuro[n]; if(ile_opuszcza<=k) { ile_zdalnych=zdalne[n]; ile_wolnych=wolne[n]; ile_biuro=biuro[n]; if(k-ile_opuszcza>=ile_zdalnych) { wyn=max(wyn, ile_wolnych+ile_zdalnych+ile_biuro); } else { wyn=max(wyn, ile_wolnych+k-ile_opuszcza+ile_biuro); } } cout << wyn << endl; } |