Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #pragma GCC optimize("fast-math")
- using namespace std;
- int n,m,k;
- char q[12][12];
- map <pair<vector<unsigned char>,pair<unsigned char,unsigned char>>,pair<short int,pair<unsigned char, unsigned char>>> ans;
- pair<short int,pair<unsigned char, unsigned char>> solve (vector <unsigned char> u,unsigned char cur, unsigned char u1) {
- 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}}];
- if (cur==1) {
- unsigned char i,j,e=4;
- for (i=u1;i<n;i++) { if (u[i]==1) {
- for (j=0;j<m;j++) {
- if (u[j+n]==1 && q[i][j]=='Y') {
- e++;
- }
- }
- }
- }
- ans[{u,{cur,u1}}]={0,{0,e}}; return ans[{u,{cur,u1}}];
- }
- pair<int,pair<int,int>> tt;
- for (unsigned char i=u1;i<=n-cur;i++) {
- for (unsigned char j=0;j<m;j++) {
- if (u[i]==1 && u[j+n]==1 && q[i][j]=='Y') {
- u[i]=0;
- u[j+n]=0;
- pair<short int,pair<unsigned char, unsigned char>> y=solve(u,cur-1,i+1);
- tt.first+=y.first;
- tt.second.first+=y.second.first;
- tt.second.second+=y.second.second-4;
- // if (tt.first>=100000) {cout<<"!!!\n"; }
- // if (tt.second.second>=256) {tt.second.first++; tt.second.second-=256; }
- // if (tt.second.first>=256) {tt.first++; tt.second.first-=256; }
- u[i]=1;
- u[j+n]=1;
- }
- }
- }
- tt.second.second+=4;
- while (tt.second.second<0) { tt.second.second+=256; tt.second.first--; }
- while (tt.second.first<0) {tt.second.first+=256; tt.first--;}
- tt.second.first+=tt.second.second/256; tt.second.second%=256;
- tt.first+=tt.second.first/256; tt.second.first%=256;
- if (tt.first<0 || tt.second.first<0 || tt.second.second<0) cout<<"!!!";
- ans[{u,{cur,u1}}]=tt;
- return ans[{u,{cur,u1}}];
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- /* --------- */
- cin>>n>>m>>k;
- int sum=0;
- for (int i=0;i<n;i++) {
- for (int j=0;j<m;j++) cin>>q[i][j];
- }
- if (k>min(n,m)) {cout<<"0"; return 0; }
- vector <unsigned char> f(n+m);
- for (int i=0;i<n+m;i++) f[i]=1;
- pair<short int,pair<unsigned char, unsigned char>> e=solve(f,k,0);
- cout<<256*256*e.first+256*e.second.first+e.second.second-4<<" ";
- //cout<<int(e.first)<<" "<<int(e.second.first)<<" "<<int(e.second.second)<<"\n";
- ///fak[k];
- /* --------- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement