Advertisement
cosenza987

Untitled

Dec 12th, 2023
809
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     //ios_base::sync_with_stdio(false);
  9.     //cin.tie(nullptr);
  10.     freopen("in.txt", "r", stdin);
  11.     freopen("out.txt", "w", stdout);
  12.     string s;
  13.     long long ans = 0;
  14.     while(cin >> s) {
  15.         string ss;
  16.         cin >> ss;
  17.         stringstream X(ss);
  18.         vector<int> v;
  19.         string tmp;
  20.         while(getline(X, tmp, ',')) {
  21.             v.push_back(stoi(tmp));
  22.         }
  23.         s = s + '?' + s + '?' + s + '?' + s + '?' + s;
  24.         vector<int> y = v;
  25.         v.insert(v.end(), y.begin(), y.end());
  26.         v.insert(v.end(), y.begin(), y.end());
  27.         v.insert(v.end(), y.begin(), y.end());
  28.         v.insert(v.end(), y.begin(), y.end());
  29.         int n = s.size(), m = v.size();
  30.         vector<vector<vector<long long>>> dp(2 * n + 1, vector<vector<long long>>(m + 1, vector<long long>(2, -1)));
  31.         function<long long(int, int, bool)> calc = [&](int i, int j, bool placed) {
  32.             if(i > n and !placed) return dp[i][j][placed] = 0;
  33.             if(i > n + 1) return dp[i][j][placed] = 0;
  34.             if(dp[i][j][placed] != -1) return dp[i][j][placed];
  35.             if(placed) {
  36.                 for(int k = i - v[j - 1] - 1; k < i - 1; k++) {
  37.                     if(s[k] == '.') {
  38.                         return dp[i][j][placed] = 0;
  39.                     }
  40.                 }
  41.                 if(i != n + 1) {
  42.                     if(s[i - 1] == '#') return dp[i][j][placed] = 0;
  43.                 }
  44.             }
  45.             if(j == m) {
  46.                 bool ok = true;
  47.                 for(int k = i; k < n; k++) {
  48.                     ok &= (s[k] != '#');
  49.                 }
  50.                 return dp[i][j][placed] = ok;
  51.             }
  52.             long long ans = 0;
  53.             if(s[i] != '.') {
  54.                 ans += calc(i + v[j] + 1, j + 1, true);
  55.             }
  56.             if(s[i] != '#') {
  57.                 ans += calc(i + 1, j, false);
  58.             }
  59.             return dp[i][j][placed] = ans;
  60.         };
  61.         ans += calc(0, 0, false);
  62.     }
  63.     cout << ans << "\n";
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement