fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3.  
  4. int n;
  5. int dp[1<<4][1<<4][1<<6][1<<10];
  6.  
  7. int f(int x, int y, int z, int state) {
  8.     if (z < 0) return 0;
  9.     if (y < 0) return f(x-1, n-1, z, state >> 1);
  10.     if (x < 0) return (z == 0);
  11.  
  12.     int &ret = dp[x][y][z][state];
  13.     if (ret != -1) return ret;
  14.  
  15.     ret = f(x, y-1, z-1, state | (1 << (y+1)));
  16.     if ( ((state >> (y-1)) & 1) | ((state >> (y+1)) & 1) ) return ret;
  17.     return ret += f(x, y-1, z, state);
  18. }
  19.  
  20. int main() {
  21.     memset(dp, -1, sizeof dp);
  22.     scanf("%d", &n);
  23.     printf("%d\n", f(n-1, n-1, (n*n) >> 1, 0));
  24.     return 0;
  25. }
  26.  
Success #stdin #stdout 0.04s 68288KB
comments (?)
stdin
copy 
8
stdout
copy 
6148
https://ideone.com/qlVEWQ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!