Advertisement
Guest User

Untitled

a guest
Jun 20th, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.85 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement