#include <iostream> #include <vector> #include <array> #define NUMBER_OF_STATUSES 3 #define MAX_N 8000 #define CACHE_SIZE MAX_N*MAX_N*NUMBER_OF_STATUSES #define CACHE_INIT_VAL (-10000) class PraSolver { int n{}; int k{}; int t{}; std::string segments; std::array<int, MAX_N> cummulativeSumOfOfficeMeetings{}; std::array<int, MAX_N> cummulativeSumOfRemoteMeetings{}; std::array<int, MAX_N> cummulativeSumOfBreaks{}; public: PraSolver() { std::cin >> n >> k >> t >> segments; cummulativeSumOfOfficeMeetings[0] = segments[0] == '1' ? 1 : 0; for(int i = 1; i < segments.size(); i++) { cummulativeSumOfOfficeMeetings[i] = cummulativeSumOfOfficeMeetings[i-1]; if(segments[i] == '1') { cummulativeSumOfOfficeMeetings[i]++; } } cummulativeSumOfRemoteMeetings[0] = segments[0] == '2' ? 1 : 0; for(int i = 1; i < segments.size(); i++) { cummulativeSumOfRemoteMeetings[i] = cummulativeSumOfRemoteMeetings[i-1]; if(segments[i] == '2') { cummulativeSumOfRemoteMeetings[i]++; } } cummulativeSumOfBreaks[0] = segments[0] == '3' ? 1 : 0; for(int i = 1; i < segments.size(); i++) { cummulativeSumOfBreaks[i] = cummulativeSumOfBreaks[i-1]; if(segments[i] == '3') { cummulativeSumOfBreaks[i]++; } } } int solve() const { return std::max(solveFullyRemote(), solveWithOfficeTravel()); } private: int solveFullyRemote() const { int remoteSegments = n; int remoteMeetings = getRange(0, n, cummulativeSumOfRemoteMeetings); int unavoidableSkippedOfficeMeetings = getRange(0, n, cummulativeSumOfOfficeMeetings); int kLeft = k - unavoidableSkippedOfficeMeetings; if (kLeft < 0) { return -1; } int meetingFromHomeCount = kLeft >= remoteMeetings ? 0 : remoteMeetings - kLeft; return remoteSegments - meetingFromHomeCount; } int solveWithOfficeTravel() const { int best = -1; for(int i = 0; i < n - t - t; i++) { for(int j = i + t; j < n - t + 1; j++) { best = std::max(best, solveWithSpecificOfficeTravel(i, j)); } } return best; } int solveWithSpecificOfficeTravel(int startTravelSegment, int startReturnSegment) const { // first home range = 0 --- startTravelSegment // second home range = (startReturnSegment + t) --- n int remoteSegments = n - t - startReturnSegment + startTravelSegment; int remoteMeetings = getRange(0, startTravelSegment, cummulativeSumOfRemoteMeetings) + getRange(startReturnSegment + t, n, cummulativeSumOfRemoteMeetings); int unavoidableSkippedOfficeMeetings = getRange(0, startTravelSegment + t, cummulativeSumOfOfficeMeetings) + getRange(startReturnSegment, n, cummulativeSumOfOfficeMeetings); int unavoidableSkippedRemoteMeetings = getRange(startTravelSegment, startTravelSegment + t, cummulativeSumOfRemoteMeetings) + getRange(startReturnSegment, startReturnSegment + t, cummulativeSumOfRemoteMeetings); int kLeft = k - unavoidableSkippedRemoteMeetings - unavoidableSkippedOfficeMeetings; if (kLeft < 0) { return -1; } int meetingFromHomeCount = kLeft >= remoteMeetings ? 0 : remoteMeetings - kLeft; return remoteSegments - meetingFromHomeCount; } int getRange(int startSegment, int exclusiveEnd, const std::array<int, MAX_N>& cummulativeSum) const { if(exclusiveEnd <= startSegment) return 0; int lowerValue = startSegment == 0 ? 0 : cummulativeSum[startSegment - 1]; int higherValue = exclusiveEnd - 1 >= n ? cummulativeSum[n - 1] : cummulativeSum[exclusiveEnd - 1]; return higherValue - lowerValue; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); PraSolver solver; int result = solver.solve(); std::cout << result; 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 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 107 | #include <iostream> #include <vector> #include <array> #define NUMBER_OF_STATUSES 3 #define MAX_N 8000 #define CACHE_SIZE MAX_N*MAX_N*NUMBER_OF_STATUSES #define CACHE_INIT_VAL (-10000) class PraSolver { int n{}; int k{}; int t{}; std::string segments; std::array<int, MAX_N> cummulativeSumOfOfficeMeetings{}; std::array<int, MAX_N> cummulativeSumOfRemoteMeetings{}; std::array<int, MAX_N> cummulativeSumOfBreaks{}; public: PraSolver() { std::cin >> n >> k >> t >> segments; cummulativeSumOfOfficeMeetings[0] = segments[0] == '1' ? 1 : 0; for(int i = 1; i < segments.size(); i++) { cummulativeSumOfOfficeMeetings[i] = cummulativeSumOfOfficeMeetings[i-1]; if(segments[i] == '1') { cummulativeSumOfOfficeMeetings[i]++; } } cummulativeSumOfRemoteMeetings[0] = segments[0] == '2' ? 1 : 0; for(int i = 1; i < segments.size(); i++) { cummulativeSumOfRemoteMeetings[i] = cummulativeSumOfRemoteMeetings[i-1]; if(segments[i] == '2') { cummulativeSumOfRemoteMeetings[i]++; } } cummulativeSumOfBreaks[0] = segments[0] == '3' ? 1 : 0; for(int i = 1; i < segments.size(); i++) { cummulativeSumOfBreaks[i] = cummulativeSumOfBreaks[i-1]; if(segments[i] == '3') { cummulativeSumOfBreaks[i]++; } } } int solve() const { return std::max(solveFullyRemote(), solveWithOfficeTravel()); } private: int solveFullyRemote() const { int remoteSegments = n; int remoteMeetings = getRange(0, n, cummulativeSumOfRemoteMeetings); int unavoidableSkippedOfficeMeetings = getRange(0, n, cummulativeSumOfOfficeMeetings); int kLeft = k - unavoidableSkippedOfficeMeetings; if (kLeft < 0) { return -1; } int meetingFromHomeCount = kLeft >= remoteMeetings ? 0 : remoteMeetings - kLeft; return remoteSegments - meetingFromHomeCount; } int solveWithOfficeTravel() const { int best = -1; for(int i = 0; i < n - t - t; i++) { for(int j = i + t; j < n - t + 1; j++) { best = std::max(best, solveWithSpecificOfficeTravel(i, j)); } } return best; } int solveWithSpecificOfficeTravel(int startTravelSegment, int startReturnSegment) const { // first home range = 0 --- startTravelSegment // second home range = (startReturnSegment + t) --- n int remoteSegments = n - t - startReturnSegment + startTravelSegment; int remoteMeetings = getRange(0, startTravelSegment, cummulativeSumOfRemoteMeetings) + getRange(startReturnSegment + t, n, cummulativeSumOfRemoteMeetings); int unavoidableSkippedOfficeMeetings = getRange(0, startTravelSegment + t, cummulativeSumOfOfficeMeetings) + getRange(startReturnSegment, n, cummulativeSumOfOfficeMeetings); int unavoidableSkippedRemoteMeetings = getRange(startTravelSegment, startTravelSegment + t, cummulativeSumOfRemoteMeetings) + getRange(startReturnSegment, startReturnSegment + t, cummulativeSumOfRemoteMeetings); int kLeft = k - unavoidableSkippedRemoteMeetings - unavoidableSkippedOfficeMeetings; if (kLeft < 0) { return -1; } int meetingFromHomeCount = kLeft >= remoteMeetings ? 0 : remoteMeetings - kLeft; return remoteSegments - meetingFromHomeCount; } int getRange(int startSegment, int exclusiveEnd, const std::array<int, MAX_N>& cummulativeSum) const { if(exclusiveEnd <= startSegment) return 0; int lowerValue = startSegment == 0 ? 0 : cummulativeSum[startSegment - 1]; int higherValue = exclusiveEnd - 1 >= n ? cummulativeSum[n - 1] : cummulativeSum[exclusiveEnd - 1]; return higherValue - lowerValue; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); PraSolver solver; int result = solver.solve(); std::cout << result; return 0; } |