SHARE
TWEET

Untitled

a guest Jun 20th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4.  
  5.  
  6.  
  7. #pragma GCC optimize("fast-math")
  8.  
  9.  
  10. using namespace std;
  11.  int n,m,k;
  12. char q[12][12];
  13.  
  14. map <pair<vector<unsigned char>,pair<unsigned char,unsigned char>>,pair<short int,pair<unsigned char, unsigned char>>> ans;
  15.  
  16. pair<short int,pair<unsigned char, unsigned char>> solve (vector <unsigned char> u,unsigned char cur, unsigned char u1) {
  17.      
  18.  
  19.     if (ans[{u,{cur,u1}}].first!=0 || ans[{u,{cur,u1}}].second.first!=0 || ans[{u,{cur,u1}}].second.second!=0) return ans[{u,{cur,u1}}];
  20.    
  21.     if (cur==1) {
  22.         unsigned char i,j,e=4;
  23.         for (i=u1;i<n;i++) { if (u[i]==1) {
  24.         for (j=0;j<m;j++) {
  25.             if (u[j+n]==1 && q[i][j]=='Y') {
  26.                 e++;
  27.             }
  28.                    
  29.                
  30.         }
  31.         }
  32.     }
  33.     ans[{u,{cur,u1}}]={0,{0,e}}; return ans[{u,{cur,u1}}];
  34.     }
  35.      
  36.     pair<int,pair<int,int>> tt;
  37.  
  38.     for (unsigned char i=u1;i<=n-cur;i++) {
  39.         for (unsigned char j=0;j<m;j++) {
  40.             if (u[i]==1 && u[j+n]==1 && q[i][j]=='Y') {
  41.                 u[i]=0;
  42.                 u[j+n]=0;
  43.                 pair<short int,pair<unsigned char, unsigned char>> y=solve(u,cur-1,i+1);
  44.                 tt.first+=y.first;
  45.                 tt.second.first+=y.second.first;
  46.                 tt.second.second+=y.second.second-4;
  47.                
  48.               //  if (tt.first>=100000) {cout<<"!!!\n"; }
  49.                // if (tt.second.second>=256) {tt.second.first++; tt.second.second-=256; }
  50.                // if (tt.second.first>=256) {tt.first++; tt.second.first-=256; }
  51.                 u[i]=1;
  52.                 u[j+n]=1;
  53.             }
  54.                    
  55.                
  56.         }
  57.          
  58.     }
  59.     tt.second.second+=4;
  60.     while (tt.second.second<0) { tt.second.second+=256; tt.second.first--; }
  61.     while (tt.second.first<0) {tt.second.first+=256; tt.first--;}
  62.     tt.second.first+=tt.second.second/256; tt.second.second%=256;
  63.                 tt.first+=tt.second.first/256; tt.second.first%=256;
  64.                 if (tt.first<0 || tt.second.first<0 || tt.second.second<0) cout<<"!!!";
  65.     ans[{u,{cur,u1}}]=tt;
  66.     return ans[{u,{cur,u1}}];
  67. }
  68.    
  69.    
  70. signed main() {
  71.     ios_base::sync_with_stdio(0);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.        
  75.      /* --------- */
  76.        
  77.      
  78.     cin>>n>>m>>k;
  79.       int sum=0;
  80.     for (int i=0;i<n;i++) {
  81.         for (int j=0;j<m;j++) cin>>q[i][j];
  82.     }
  83.     if (k>min(n,m)) {cout<<"0"; return 0; }
  84.     vector <unsigned char> f(n+m);
  85.     for (int i=0;i<n+m;i++) f[i]=1;
  86.      
  87.     pair<short int,pair<unsigned char, unsigned char>> e=solve(f,k,0);
  88.     cout<<256*256*e.first+256*e.second.first+e.second.second-4<<" ";
  89.     //cout<<int(e.first)<<" "<<int(e.second.first)<<" "<<int(e.second.second)<<"\n";
  90.      ///fak[k];
  91.    /* --------- */
  92.     return 0;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top