#include <cstdio> #include <algorithm> #define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i) using namespace std; int n, max_skip, travel_time; char P[8005]; int result; int total_office_meetings, office_meetings[8005]; int total_remote_meetings, remote_meetings[8005]; inline int get_office_meetings(int up_to_time) { if (up_to_time >= n) return total_office_meetings; if (up_to_time < 0) return 0; return office_meetings[up_to_time]; } inline int get_remote_meetings(int up_to_time) { if (up_to_time >= n) return total_remote_meetings; if (up_to_time < 0) return 0; return remote_meetings[up_to_time]; } int main() { scanf("%d %d %d", &n, &max_skip, &travel_time); scanf("%s", P); // Scan type of meetings total_office_meetings = total_remote_meetings = 0; FOR(i,0,n) { if (P[i] == '1') ++total_office_meetings; else if (P[i] == '2') ++total_remote_meetings; office_meetings[i] = total_office_meetings; remote_meetings[i] = total_remote_meetings; } result = -1; // Case 1 - whole time at home if (total_office_meetings <= max_skip) result = max(result, n - max(0, total_remote_meetings + total_office_meetings - max_skip)); // Case 2 - one time in the office (at least for one hour) FOR(outside_length, 2*travel_time+1, n+1) { int home_lenght = n - outside_length; // If there is no possibility to have more free time as currently best result - just stop if ((result != -1) && (home_lenght < result)) break; // For every segment of lenght 'outside_length' FOR(outside_start, 0, n-outside_length+1) { int outside_end = outside_start + outside_length - 1; int office_start = outside_start + travel_time; int office_end = outside_end - travel_time; int available_skip = max_skip; available_skip -= get_remote_meetings(outside_end) - get_remote_meetings(office_end); available_skip -= get_remote_meetings(office_start-1) - get_remote_meetings(outside_start-1); available_skip -= total_office_meetings - get_office_meetings(office_end); available_skip -= get_office_meetings(office_start-1); if (available_skip < 0) continue; int home_remote = total_remote_meetings - get_remote_meetings(outside_end) + get_remote_meetings(outside_start-1); int local_result = home_lenght - max(0, home_remote - available_skip); result = max(result, local_result); } } printf("%d\n", result); }
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 | #include <cstdio> #include <algorithm> #define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i) using namespace std; int n, max_skip, travel_time; char P[8005]; int result; int total_office_meetings, office_meetings[8005]; int total_remote_meetings, remote_meetings[8005]; inline int get_office_meetings(int up_to_time) { if (up_to_time >= n) return total_office_meetings; if (up_to_time < 0) return 0; return office_meetings[up_to_time]; } inline int get_remote_meetings(int up_to_time) { if (up_to_time >= n) return total_remote_meetings; if (up_to_time < 0) return 0; return remote_meetings[up_to_time]; } int main() { scanf("%d %d %d", &n, &max_skip, &travel_time); scanf("%s", P); // Scan type of meetings total_office_meetings = total_remote_meetings = 0; FOR(i,0,n) { if (P[i] == '1') ++total_office_meetings; else if (P[i] == '2') ++total_remote_meetings; office_meetings[i] = total_office_meetings; remote_meetings[i] = total_remote_meetings; } result = -1; // Case 1 - whole time at home if (total_office_meetings <= max_skip) result = max(result, n - max(0, total_remote_meetings + total_office_meetings - max_skip)); // Case 2 - one time in the office (at least for one hour) FOR(outside_length, 2*travel_time+1, n+1) { int home_lenght = n - outside_length; // If there is no possibility to have more free time as currently best result - just stop if ((result != -1) && (home_lenght < result)) break; // For every segment of lenght 'outside_length' FOR(outside_start, 0, n-outside_length+1) { int outside_end = outside_start + outside_length - 1; int office_start = outside_start + travel_time; int office_end = outside_end - travel_time; int available_skip = max_skip; available_skip -= get_remote_meetings(outside_end) - get_remote_meetings(office_end); available_skip -= get_remote_meetings(office_start-1) - get_remote_meetings(outside_start-1); available_skip -= total_office_meetings - get_office_meetings(office_end); available_skip -= get_office_meetings(office_start-1); if (available_skip < 0) continue; int home_remote = total_remote_meetings - get_remote_meetings(outside_end) + get_remote_meetings(outside_start-1); int local_result = home_lenght - max(0, home_remote - available_skip); result = max(result, local_result); } } printf("%d\n", result); } |