#include<bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define VI vector<int> #define PII pair<int,int> #define st first #define nd second #define mp make_pair #define pb push_back #define lint long long int #define debug(x) {cerr <<#x <<" = " <<x <<endl; } #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }} #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }} #define make( x) int (x); scanf("%d",&(x)); #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y)); #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z)); #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define IOS ios_base::sync_with_stdio(0) #define HEAP priority_queue #define read( x) scanf("%d",&(x)); #define read2( x, y) scanf("%d%d",&(x),&(y)); #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z)); #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); using namespace std; int n, k, t; char s[8005]; int cnt[8005][3]; int ile(int a, int b, int kogo) { if (b < a) return 0; return cnt[b][kogo]-(a==0? 0 : cnt[a-1][kogo]); } const int BIURO = 0; const int ZDALNE= 1; const int WOLNE = 2; bool musze_do_biura() { if (cnt[n-1][BIURO] > k) return true; return false; } int main() { read3(n, k, t); scanf("%s", s); FOR(j,0,3) { cnt[0][j] = (s[0] == ('1'+j)) ? 1 : 0; FOR(i,1,n) cnt[i][j] = cnt[i-1][j] + ((s[i] == ('1'+j)) ? 1 : 0); } if (!musze_do_biura()) { int ans = n - max(0, cnt[n-1][BIURO] + cnt[n-1][ZDALNE] - k); printf("%d\n", ans); return 0; } int best = -1; // 0,1,...,n-1 // [0, ruszam - 1] <- dom // [ruszam, ruszam+t-1] <- auto // [ruszam+t, ruszam+t+w_biurze-1] <- biuro // [ruszam+t+w_biurze, ruszam+t+w_biurze+t-1] <- auto // [ruszma+w_biurze+2t, n-1] <- dom for (int w_biurze = 1; w_biurze + 2*t <= n; w_biurze++) { for (int ruszam = 0; ruszam + w_biurze+2*t <= n; ruszam++) { int omijam_tam = ile(ruszam, ruszam+t-1, BIURO) + ile(ruszam, ruszam+t-1,ZDALNE); int omijam_z_powrotem = ile(ruszam+t+w_biurze, ruszam+t+w_biurze+t-1, BIURO) + ile(ruszam+t+w_biurze, ruszam+t+w_biurze+t-1,ZDALNE); int omijam_w_domu = ile(0, ruszam-1, BIURO) + ile(ruszam+w_biurze+2*t, n-1, BIURO); if (omijam_tam + omijam_z_powrotem + omijam_w_domu <= k) { int jeszcze_moge_ominac = k - omijam_tam - omijam_z_powrotem - omijam_w_domu; int dobre = ile(0, ruszam-1, WOLNE) + ile(ruszam+w_biurze+2*t, n-1, WOLNE); dobre += ile(0, ruszam-1, BIURO) + ile(ruszam+w_biurze+2*t, n-1, BIURO); int zdalne_w_domu = ile(0, ruszam-1, ZDALNE) + ile(ruszam+w_biurze+2*t, n-1, ZDALNE); dobre += min(jeszcze_moge_ominac, zdalne_w_domu); best = max(best, dobre); } } } printf("%d\n", best); }
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 | #include<bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define VI vector<int> #define PII pair<int,int> #define st first #define nd second #define mp make_pair #define pb push_back #define lint long long int #define debug(x) {cerr <<#x <<" = " <<x <<endl; } #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }} #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }} #define make( x) int (x); scanf("%d",&(x)); #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y)); #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z)); #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define IOS ios_base::sync_with_stdio(0) #define HEAP priority_queue #define read( x) scanf("%d",&(x)); #define read2( x, y) scanf("%d%d",&(x),&(y)); #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z)); #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); using namespace std; int n, k, t; char s[8005]; int cnt[8005][3]; int ile(int a, int b, int kogo) { if (b < a) return 0; return cnt[b][kogo]-(a==0? 0 : cnt[a-1][kogo]); } const int BIURO = 0; const int ZDALNE= 1; const int WOLNE = 2; bool musze_do_biura() { if (cnt[n-1][BIURO] > k) return true; return false; } int main() { read3(n, k, t); scanf("%s", s); FOR(j,0,3) { cnt[0][j] = (s[0] == ('1'+j)) ? 1 : 0; FOR(i,1,n) cnt[i][j] = cnt[i-1][j] + ((s[i] == ('1'+j)) ? 1 : 0); } if (!musze_do_biura()) { int ans = n - max(0, cnt[n-1][BIURO] + cnt[n-1][ZDALNE] - k); printf("%d\n", ans); return 0; } int best = -1; // 0,1,...,n-1 // [0, ruszam - 1] <- dom // [ruszam, ruszam+t-1] <- auto // [ruszam+t, ruszam+t+w_biurze-1] <- biuro // [ruszam+t+w_biurze, ruszam+t+w_biurze+t-1] <- auto // [ruszma+w_biurze+2t, n-1] <- dom for (int w_biurze = 1; w_biurze + 2*t <= n; w_biurze++) { for (int ruszam = 0; ruszam + w_biurze+2*t <= n; ruszam++) { int omijam_tam = ile(ruszam, ruszam+t-1, BIURO) + ile(ruszam, ruszam+t-1,ZDALNE); int omijam_z_powrotem = ile(ruszam+t+w_biurze, ruszam+t+w_biurze+t-1, BIURO) + ile(ruszam+t+w_biurze, ruszam+t+w_biurze+t-1,ZDALNE); int omijam_w_domu = ile(0, ruszam-1, BIURO) + ile(ruszam+w_biurze+2*t, n-1, BIURO); if (omijam_tam + omijam_z_powrotem + omijam_w_domu <= k) { int jeszcze_moge_ominac = k - omijam_tam - omijam_z_powrotem - omijam_w_domu; int dobre = ile(0, ruszam-1, WOLNE) + ile(ruszam+w_biurze+2*t, n-1, WOLNE); dobre += ile(0, ruszam-1, BIURO) + ile(ruszam+w_biurze+2*t, n-1, BIURO); int zdalne_w_domu = ile(0, ruszam-1, ZDALNE) + ile(ruszam+w_biurze+2*t, n-1, ZDALNE); dobre += min(jeszcze_moge_ominac, zdalne_w_domu); best = max(best, dobre); } } } printf("%d\n", best); } |