day19b.cpp (1192B)
1 #include <algorithm> 2 #include <cstdint> 3 #include <iostream> 4 #include <map> 5 #include <queue> 6 #include <ranges> 7 #include <set> 8 #include <sstream> 9 #include <string> 10 #include <string_view> 11 #include <vector> 12 using namespace std; 13 14 vector<string_view> gettowels(const string_view& line) { 15 vector<string_view> ret; 16 unsigned sz = line.size(); 17 for (int i = 0, j = 0; j != -1; i = j+2) { 18 j = line.find(",", i); 19 ret.push_back(line.substr(i, (j == -1 ? sz : j) - i)); 20 } 21 return ret; 22 } 23 24 int64_t f(const string_view& p, const vector<string_view>& towels, vector<int64_t>& mem) { 25 unsigned lp = p.size(); 26 if (lp == 0) return 1; 27 if (mem[lp] != -1) return mem[lp]; 28 int64_t ret = 0; 29 for (auto t : towels) { 30 unsigned lt = t.size(); 31 if (t == p.substr(0, lt)) 32 ret += f(p.substr(lt, lp - lt), towels, mem); 33 } 34 return (mem[lp] = ret); 35 } 36 37 int main() { 38 string line; 39 getline(cin, line); 40 auto towels = gettowels(line); 41 getline(cin, line); 42 vector<string> patterns; 43 while (getline(cin, line)) 44 patterns.push_back(line); 45 vector<int64_t> mem(1000); 46 int64_t count = 0; 47 for (auto p : patterns) { 48 for (auto& m : mem) m = -1; 49 count += f(p, towels, mem); 50 } 51 cout << count << endl; 52 return 0; 53 }