Raslboyy

75Bv2

Oct 11th, 2019
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. bool bit(ll var, int pos) {
  11.     return ((var >> pos) & 1);
  12. }
  13.  
  14. int main() {
  15.     ifstream fin("input.txt");
  16.     ofstream fout("output.txt");
  17.  
  18.     int n, m;
  19.     fin >> n >> m;
  20.     if (n > m)
  21.         swap(n, m);
  22.     vector<vector<vector<ll>>> dp(n + 10, vector<vector<ll>>(m + 10, vector<ll>(1 << n + 1)));
  23.    
  24.     for (int prof = 0; prof < (1 << n + 1); prof++)
  25.         dp[0][1][prof] = 1;
  26.  
  27.     for (int j = 1; j < m; j++) {
  28.         for (int i = 0; i < n; i++) {
  29.             for (int prof = 0; prof < (1 << n + 1); prof++) {
  30.                 if (i == n - 1) {
  31.                     dp[0][j + 1][((prof << 1) & ~(1 << n + 1))] += dp[i][j][prof];
  32.                     dp[0][j + 1][((prof << 1) & ~(1 << n + 1)) | 1] += dp[i][j][prof];
  33.                 }
  34.                 else {
  35.                     int sum = bit(prof, i) + bit(prof, i + 1) + bit(prof, i + 2);
  36.                     if (sum + 1 != 4) dp[i + 1][j][(prof | (1 << i))] += dp[i][j][prof];
  37.                     if (sum != 0) dp[i + 1][j][(prof & (~(1 << i)))] += dp[i][j][prof];
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     ll sum = 0;
  43.     for (ll a : dp[n - 1][m - 1]) sum += a;
  44.     fout << sum << endl;
  45.  
  46.  
  47.     fin.close();
  48.     fout.close();
  49.     return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment