#include <iostream> #include <string> #include <vector> int calculateMaxValidMeetings(const std::string& schedule, int n, int k, int t) { std::vector<std::vector<int>> left(schedule.length(), std::vector<int>(3, 0)); std::vector<std::vector<int>> right(schedule.length(), std::vector<int>(3, 0)); // Obliczamy liczniki z lewej strony for (int i = 1; i < schedule.length(); i++) { left[i] = left[i-1]; if (schedule[i-1] >= '1' && schedule[i-1] <= '3') { left[i][schedule[i-1] - '1']++; } } // Obliczamy liczniki z prawej strony for (int i = schedule.length()-2; i >= 0; i--) { right[i] = right[i+1]; if (schedule[i+1] >= '1' && schedule[i+1] <= '3') { right[i][schedule[i+1] - '1']++; } } std::vector<int> turtle(n, 0); int meetingCounter = 0; int turtleBegin = 0; int turtleEnd = t-1; for(int i = 0; i < t; i++) { if(schedule[i] == '1' || schedule[i] == '2') { meetingCounter++; } } turtle[turtleBegin] = meetingCounter; turtleEnd++; turtleBegin++; while(turtleEnd < n) { if(schedule[turtleBegin-1] == '1' || schedule[turtleBegin-1] == '2') { meetingCounter--; } if(schedule[turtleEnd] == '1' || schedule[turtleEnd] == '2') { meetingCounter++; } turtle[turtleBegin] = meetingCounter; turtleBegin++; turtleEnd++; } int max = -1; // Główna logika for(int i = 0; i < n; i++) { for(int j = i+t; j <= n-t; j++) { int validationSum = turtle[i] + turtle[j] + left[i][0] + right[j +t - 1][0]; if(validationSum > k) { continue; } int result = left[i][0] + right[j +t -1][0] + left[i][2] + right[j +t -1][2]; int canSkip = k - validationSum; int freeCandidates = left[i][1] + right[j +t-1][1]; int toAdd = freeCandidates > canSkip ? canSkip : freeCandidates; if(result + toAdd > max) { max = result + toAdd; } } } // Sprawdzenie pierwszej pozycji if (schedule[0] == '1') right[0][0]++; if (schedule[0] == '2') right[0][1]++; if (schedule[0] == '3') right[0][2]++; int validationSum = right[0][0]; if (validationSum <= k) { int result = right[0][0] + right[0][2]; int canSkip = k - validationSum; int freeCandidates = right[0][1]; int toAdd = freeCandidates > canSkip ? canSkip : freeCandidates; if (result + toAdd > max) { max = result + toAdd; } } return max; } //#if !defined(GTEST_TESTING) int main() { int n, k, t; std::cin >> n >> k >> t; std::string schedule; std::cin >> schedule; std::cout << calculateMaxValidMeetings(schedule, n, k, t); return 0; } //#endif
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 95 96 97 98 99 100 101 102 103 104 105 106 | #include <iostream> #include <string> #include <vector> int calculateMaxValidMeetings(const std::string& schedule, int n, int k, int t) { std::vector<std::vector<int>> left(schedule.length(), std::vector<int>(3, 0)); std::vector<std::vector<int>> right(schedule.length(), std::vector<int>(3, 0)); // Obliczamy liczniki z lewej strony for (int i = 1; i < schedule.length(); i++) { left[i] = left[i-1]; if (schedule[i-1] >= '1' && schedule[i-1] <= '3') { left[i][schedule[i-1] - '1']++; } } // Obliczamy liczniki z prawej strony for (int i = schedule.length()-2; i >= 0; i--) { right[i] = right[i+1]; if (schedule[i+1] >= '1' && schedule[i+1] <= '3') { right[i][schedule[i+1] - '1']++; } } std::vector<int> turtle(n, 0); int meetingCounter = 0; int turtleBegin = 0; int turtleEnd = t-1; for(int i = 0; i < t; i++) { if(schedule[i] == '1' || schedule[i] == '2') { meetingCounter++; } } turtle[turtleBegin] = meetingCounter; turtleEnd++; turtleBegin++; while(turtleEnd < n) { if(schedule[turtleBegin-1] == '1' || schedule[turtleBegin-1] == '2') { meetingCounter--; } if(schedule[turtleEnd] == '1' || schedule[turtleEnd] == '2') { meetingCounter++; } turtle[turtleBegin] = meetingCounter; turtleBegin++; turtleEnd++; } int max = -1; // Główna logika for(int i = 0; i < n; i++) { for(int j = i+t; j <= n-t; j++) { int validationSum = turtle[i] + turtle[j] + left[i][0] + right[j +t - 1][0]; if(validationSum > k) { continue; } int result = left[i][0] + right[j +t -1][0] + left[i][2] + right[j +t -1][2]; int canSkip = k - validationSum; int freeCandidates = left[i][1] + right[j +t-1][1]; int toAdd = freeCandidates > canSkip ? canSkip : freeCandidates; if(result + toAdd > max) { max = result + toAdd; } } } // Sprawdzenie pierwszej pozycji if (schedule[0] == '1') right[0][0]++; if (schedule[0] == '2') right[0][1]++; if (schedule[0] == '3') right[0][2]++; int validationSum = right[0][0]; if (validationSum <= k) { int result = right[0][0] + right[0][2]; int canSkip = k - validationSum; int freeCandidates = right[0][1]; int toAdd = freeCandidates > canSkip ? canSkip : freeCandidates; if (result + toAdd > max) { max = result + toAdd; } } return max; } //#if !defined(GTEST_TESTING) int main() { int n, k, t; std::cin >> n >> k >> t; std::string schedule; std::cin >> schedule; std::cout << calculateMaxValidMeetings(schedule, n, k, t); return 0; } //#endif |