codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1107C.md (3250B)


      1 Source: https://codeforces.com/problemset/problem/1107/C
      2 
      3 C. Brutality
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are playing a new famous fighting game: Kortal Mombat XII. You have to perform a brutality on your opponent's character.
     22 
     23 You are playing the game on the new generation console so your gamepad have $26$ buttons. Each button has a single lowercase Latin letter from 'a' to 'z' written on it. All the letters on buttons are pairwise distinct.
     24 
     25 You are given a sequence of hits, the $i$-th hit deals $a_i$ units of damage to the opponent's character. To perform the $i$-th hit you have to press the button $s_i$ on your gamepad. Hits are numbered from $1$ to $n$.
     26 
     27 You know that if you press some button more than $k$ times in a row then it'll break. You cherish your gamepad and don't want to break any of its buttons.
     28 
     29 To perform a brutality you have to land some of the hits of the given sequence. You are allowed to skip any of them, however changing the initial order of the sequence is prohibited. The total damage dealt is the sum of $a_i$ over all $i$ for the hits which weren't skipped.
     30 
     31 Note that if you skip the hit then the counter of consecutive presses the button won't reset.
     32 
     33 Your task is to skip some hits to deal the maximum possible total damage to the opponent's character and not break your gamepad buttons.
     34 
     35 Input
     36 
     37 The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of hits and the maximum number of times you can push the same button in a row.
     38 
     39 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the damage of the $i$-th hit.
     40 
     41 The third line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters — the sequence of hits (each character is the letter on the button you need to press to perform the corresponding hit).
     42 
     43 Output
     44 
     45 Print one integer $dmg$ — the maximum possible damage to the opponent's character you can deal without breaking your gamepad buttons.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 7 3
     53 1 5 16 18 7 2 10
     54 baaaaca
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 54
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 5 5
     67 2 4 1 3 1000
     68 aaaaa
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 1010
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 5 4
     81 2 4 1 3 1000
     82 aaaaa
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 1009
     89 ```
     90 
     91 Input
     92 
     93 ```
     94 8 1
     95 10 15 2 1 4 8 15 16
     96 qqwweerr
     97 ```
     98 
     99 Output
    100 
    101 ```
    102 41
    103 ```
    104 
    105 Input
    106 
    107 ```
    108 6 3
    109 14 18 9 19 2 15
    110 cccccc
    111 ```
    112 
    113 Output
    114 
    115 ```
    116 52
    117 ```
    118 
    119 Input
    120 
    121 ```
    122 2 1
    123 10 10
    124 qq
    125 ```
    126 
    127 Output
    128 
    129 ```
    130 10
    131 ```
    132 
    133 Note
    134 
    135 In the first example you can choose hits with numbers $[1, 3, 4, 5, 6, 7]$ with the total damage $1 + 16 + 18 + 7 + 2 + 10 = 54$.
    136 
    137 In the second example you can choose all hits so the total damage is $2 + 4 + 1 + 3 + 1000 = 1010$.
    138 
    139 In the third example you can choose all hits expect the third one so the total damage is $2 + 4 + 3 + 1000 = 1009$.
    140 
    141 In the fourth example you can choose hits with numbers $[2, 3, 6, 8]$. Only this way you can reach the maximum total damage $15 + 2 + 8 + 16 = 41$.
    142 
    143 In the fifth example you can choose only hits with numbers $[2, 4, 6]$ with the total damage $18 + 19 + 15 = 52$.
    144 
    145 In the sixth example you can change either first hit or the second hit (it does not matter) with the total damage $10$.