Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void getMaxScore(vector<string> &words, vector<int> &frequencies, vector<int> &scores, int index, int currScore, int &maxScore){
- if(index == words.size()){
- maxScore = max(maxScore, currScore);
- return;
- }
- //current word excluded
- getMaxScore(words, frequencies, scores, index + 1, currScore, maxScore);
- //deduct frequencies and add score if word included in set
- bool charLeftToUse = true;
- for(int i = 0; i < words[index].size(); i++){
- char charInWord = words[index][i];
- frequencies[charInWord - 'a']--;
- if(frequencies[charInWord - 'a'] < 0){
- charLeftToUse = false;
- }
- currScore += scores[charInWord - 'a'];
- }
- //current word included, but if there is enough frequencies of the character present in word
- if(charLeftToUse){
- getMaxScore(words, frequencies, scores, index + 1, currScore, maxScore);
- }
- //revert the state of frequencies and currScore before returning
- for(int i = 0; i < words[index].size(); i++){
- char charInWord = words[index][i];
- frequencies[charInWord - 'a']++;
- currScore -= scores[charInWord - 'a'];
- }
- }
- int main() {
- // your code goes here
- int w, f, maxScore = 0;
- cin >> w;
- vector<string> words(w);
- vector<int> frequencies(26, 0);
- vector<int> scores(26, 0);
- for(int i = 0; i < w; i++){
- cin >> words[i];
- }
- cin >> f;
- char c;
- for(int i = 0; i < f; i++){
- cin >> c;
- frequencies[c - 'a']++;
- }
- // for(int i = 0; i < frequencies.size(); i++){
- // cout << char (i + 'a') << ": " << frequencies[i] << '\n';
- // }
- for(int i = 0; i < scores.size(); i++){
- cin >> scores[i];
- }
- // for(int i = 0; i < scores.size(); i++){
- // cout << char (i + 'a') << ": " << scores[i] << '\n';
- // }
- getMaxScore(words, frequencies, scores, 0, 0, maxScore);
- cout << maxScore << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
