#include <cstdio> #include <algorithm> using namespace std; // Dla bezpieczeństwa przy n=8000 dajemy tablice minimalnie większe static const int MAXN = 8000 + 5; // Słowo z obowiązkami char s[MAXN]; // Prefix-sumy dla '1', '2', '3' int ps1[MAXN], ps2[MAXN], ps3[MAXN]; // Pomocniczy makro do pobierania liczby znaków danej kategorii w przedziale [l..r] #define GET_COUNT(ps, l, r) ( ((l) <= (r)) ? ((ps)[(r)] - (ps)[(l)-1]) : 0 ) int main(){ int n, k, t; scanf("%d %d %d", &n, &k, &t); scanf("%s", s+1); // Wczytujemy do s[1..n], żeby indeksowanie było 1‑bazowe // (s[0] niewykorzystane; s[1] to pierwszy znak) // Obliczamy prefix-sumy // ps1[i] = liczba wystąpień '1' na przedziale [1..i], itd. for(int i = 1; i <= n; i++){ ps1[i] = ps1[i-1]; ps2[i] = ps2[i-1]; ps3[i] = ps3[i-1]; if(s[i] == '1') ps1[i]++; if(s[i] == '2') ps2[i]++; if(s[i] == '3') ps3[i]++; } // Zliczamy całkowitą liczbę '1', '2', '3' int total1 = ps1[n]; int total2 = ps2[n]; int total3 = ps3[n]; // best - wynik maksymalny (liczba godzin na zadania) long long best = -1; // --------------------------------------------------- // Przypadek 1: Bajtazar nie jedzie do biura w ogóle // --------------------------------------------------- { // Wszystkie '1' w domu są opuszczone -> forcedSkip_noOffice = total1 int forcedSkip_noOffice = total1; if(forcedSkip_noOffice <= k){ // tasksBase = liczba '3' + liczba '1' long long tasksBase_noOffice = (long long)total3 + total1; // Liczba zdalnych '2' w domu, które ewentualnie możemy opuścić int optionalSkip2Home_noOffice = total2; long long canSkip2 = k - forcedSkip_noOffice; long long tasks_noOffice = tasksBase_noOffice + min<long long>(optionalSkip2Home_noOffice, canSkip2); if(tasks_noOffice > best){ best = tasks_noOffice; } } } // --------------------------------------------------- // Przypadek 2: Dokładnie jeden wyjazd do biura // --------------------------------------------------- // Wybieramy [x..y] - Bajtazar w biurze w tych godzinach // Droga "tam": [x-t .. x-1] // Droga "z powrotem": [y+1 .. y+t] // Warunek: x >= t+1, y <= n-t, oraz x <= y for(int x = t+1; x <= n - t; x++){ for(int y = x; y <= n - t; y++){ // Obliczamy liczbę '1','2' w czasie drogi (T), // bo w drodze każdy '1'/'2' jest opuszczany (forced skip). // Droga "tam": [x-t .. x-1] // Droga "z powrotem": [y+1 .. y+t] int count1_T = GET_COUNT(ps1, x-t, x-1) + GET_COUNT(ps1, y+1, y+t); int count2_T = GET_COUNT(ps2, x-t, x-1) + GET_COUNT(ps2, y+1, y+t); // W biurze [x..y] - tam nie ma skipów, bo można odbyć spotkania. int count1_O = GET_COUNT(ps1, x, y); int count2_O = GET_COUNT(ps2, x, y); // (count3_O nie jest potrzebne do skipów ani do zadań) // W domu H = całość - T - O // Zliczamy '1','2','3' w H poprzez odjęcie od total. int count1_H = total1 - (count1_T + count1_O); int count2_H = total2 - (count2_T + count2_O); // Możemy również potrzebować count3_H int count3_T = GET_COUNT(ps3, x-t, x-1) + GET_COUNT(ps3, y+1, y+t); int count3_O = GET_COUNT(ps3, x, y); int count3_H = total3 - (count3_T + count3_O); // forcedSkip = (wszystkie '1' i '2' w drodze) + (wszystkie '1' w domu) int forcedSkip = (count1_T + count2_T) + count1_H; if(forcedSkip > k){ // Zbyt wiele wymuszonych opuszczeń, pomijamy continue; } // tasksBase = liczba '3' w domu + liczba '1' w domu // bo '1' w domu też daje 1 godzinę na zadania (choć wymusza skip) long long tasksBase = (long long)count3_H + count1_H; // optionalSkip2Home = liczba '2' w domu // Każde takie '2' możemy albo uczestniczyć, albo pominąć (+1 do skip, +1 do zadań) int optionalSkip2Home = count2_H; long long canSkip2 = k - forcedSkip; long long tasks = tasksBase + min<long long>(optionalSkip2Home, canSkip2); if(tasks > best){ best = tasks; } } } // Jeśli best nadal -1, to znaczy, że nie ma planu mieszczącego się w limicie k if(best < 0){ printf("-1\n"); } else { printf("%lld\n", best); } 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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #include <cstdio> #include <algorithm> using namespace std; // Dla bezpieczeństwa przy n=8000 dajemy tablice minimalnie większe static const int MAXN = 8000 + 5; // Słowo z obowiązkami char s[MAXN]; // Prefix-sumy dla '1', '2', '3' int ps1[MAXN], ps2[MAXN], ps3[MAXN]; // Pomocniczy makro do pobierania liczby znaków danej kategorii w przedziale [l..r] #define GET_COUNT(ps, l, r) ( ((l) <= (r)) ? ((ps)[(r)] - (ps)[(l)-1]) : 0 ) int main(){ int n, k, t; scanf("%d %d %d", &n, &k, &t); scanf("%s", s+1); // Wczytujemy do s[1..n], żeby indeksowanie było 1‑bazowe // (s[0] niewykorzystane; s[1] to pierwszy znak) // Obliczamy prefix-sumy // ps1[i] = liczba wystąpień '1' na przedziale [1..i], itd. for(int i = 1; i <= n; i++){ ps1[i] = ps1[i-1]; ps2[i] = ps2[i-1]; ps3[i] = ps3[i-1]; if(s[i] == '1') ps1[i]++; if(s[i] == '2') ps2[i]++; if(s[i] == '3') ps3[i]++; } // Zliczamy całkowitą liczbę '1', '2', '3' int total1 = ps1[n]; int total2 = ps2[n]; int total3 = ps3[n]; // best - wynik maksymalny (liczba godzin na zadania) long long best = -1; // --------------------------------------------------- // Przypadek 1: Bajtazar nie jedzie do biura w ogóle // --------------------------------------------------- { // Wszystkie '1' w domu są opuszczone -> forcedSkip_noOffice = total1 int forcedSkip_noOffice = total1; if(forcedSkip_noOffice <= k){ // tasksBase = liczba '3' + liczba '1' long long tasksBase_noOffice = (long long)total3 + total1; // Liczba zdalnych '2' w domu, które ewentualnie możemy opuścić int optionalSkip2Home_noOffice = total2; long long canSkip2 = k - forcedSkip_noOffice; long long tasks_noOffice = tasksBase_noOffice + min<long long>(optionalSkip2Home_noOffice, canSkip2); if(tasks_noOffice > best){ best = tasks_noOffice; } } } // --------------------------------------------------- // Przypadek 2: Dokładnie jeden wyjazd do biura // --------------------------------------------------- // Wybieramy [x..y] - Bajtazar w biurze w tych godzinach // Droga "tam": [x-t .. x-1] // Droga "z powrotem": [y+1 .. y+t] // Warunek: x >= t+1, y <= n-t, oraz x <= y for(int x = t+1; x <= n - t; x++){ for(int y = x; y <= n - t; y++){ // Obliczamy liczbę '1','2' w czasie drogi (T), // bo w drodze każdy '1'/'2' jest opuszczany (forced skip). // Droga "tam": [x-t .. x-1] // Droga "z powrotem": [y+1 .. y+t] int count1_T = GET_COUNT(ps1, x-t, x-1) + GET_COUNT(ps1, y+1, y+t); int count2_T = GET_COUNT(ps2, x-t, x-1) + GET_COUNT(ps2, y+1, y+t); // W biurze [x..y] - tam nie ma skipów, bo można odbyć spotkania. int count1_O = GET_COUNT(ps1, x, y); int count2_O = GET_COUNT(ps2, x, y); // (count3_O nie jest potrzebne do skipów ani do zadań) // W domu H = całość - T - O // Zliczamy '1','2','3' w H poprzez odjęcie od total. int count1_H = total1 - (count1_T + count1_O); int count2_H = total2 - (count2_T + count2_O); // Możemy również potrzebować count3_H int count3_T = GET_COUNT(ps3, x-t, x-1) + GET_COUNT(ps3, y+1, y+t); int count3_O = GET_COUNT(ps3, x, y); int count3_H = total3 - (count3_T + count3_O); // forcedSkip = (wszystkie '1' i '2' w drodze) + (wszystkie '1' w domu) int forcedSkip = (count1_T + count2_T) + count1_H; if(forcedSkip > k){ // Zbyt wiele wymuszonych opuszczeń, pomijamy continue; } // tasksBase = liczba '3' w domu + liczba '1' w domu // bo '1' w domu też daje 1 godzinę na zadania (choć wymusza skip) long long tasksBase = (long long)count3_H + count1_H; // optionalSkip2Home = liczba '2' w domu // Każde takie '2' możemy albo uczestniczyć, albo pominąć (+1 do skip, +1 do zadań) int optionalSkip2Home = count2_H; long long canSkip2 = k - forcedSkip; long long tasks = tasksBase + min<long long>(optionalSkip2Home, canSkip2); if(tasks > best){ best = tasks; } } } // Jeśli best nadal -1, to znaczy, że nie ma planu mieszczącego się w limicie k if(best < 0){ printf("-1\n"); } else { printf("%lld\n", best); } return 0; } |