Submission 1452 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1452	30/05/2013 17:55:19	rlac	E - Tablero I	Accepted	94	4.9 KiB	GNU G++ 5.1.0

Code

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <vector>

#ifdef RLAC
	#define DEB(a)			clog << __LINE__ << ": " << #a << " = " << (a) << endl
	#define OUT(a, n)		for (int J = 0; J < (n); ++J)	clog << (a)[J] << " \n"[J == (n) - 1];
	#define NAME			"E"
#else
	#define DEB(a)
	#define OUT(a, n)
#endif

using namespace std;

const int MAXN = 12, MAXM = 105, MOD = 1e9 + 7;
typedef long long ll;

vector<int> d[1 << MAXN];	/* d[msk] contiene las máscaras que son compatibles con msk.	*/
ll dp[MAXM + 2][1 << MAXN];
int n, m;

/*	Computa la tabla d	*/
void go (int p, int p2, int l)
{
	if (l == n)
		d[p2].push_back(p);
	else if ((1 << l) & p)
		go(p, p2, l + 1);                       		/*  La l-ésima casilla está ocupada, continua a la próxima	*/
	else
	{
		go(p, p2 | (1 << l), l + 1);    				/*	Pone una ficha de dominó horizontal.	*/
		
		if (l < n - 1 && ((1 << (l + 1)) & p) == 0)     /*  Ni la l-ésima ni la (l + 1)-ésima casilla están ocupadas.	*/
		    go(p, p2, l + 2);                         	/*  Pone una ficha vertical (esto no afecta la siguiente columna) */
	}
}

ll solve ()
{
	for (int i = 0; i < (1 << n); ++i)
		go (i, 0, 0);
		
    dp[1][0] = 1;

for (int i = 2; i <= m + 1; ++i)
	{
		for (int msk = 0; msk < (1 << n); ++msk)
		{
			for (int j = 0; j < d[msk].size(); ++j)		/* Se recorren las máscaras que son compatibleas con msk	*/
			{
			    dp[i][msk] = (dp[i][msk] + dp[i - 1][d[msk][j]]) % MOD;
			}
		}
	}

return dp[m + 1][0];
}

int main ()
{
	//Improvement region
	ios_base::sync_with_stdio(0);
	cin.tie(0);

//Input region
	#ifdef RLAC
		system("notepad "NAME".in");
		freopen(NAME".in", "r", stdin);
		FILE * FILE_NAME = freopen(NAME".out", "w", stdout);
		int TIME = clock();
	#endif
	//Add your code here...
	cin >> n >> m;
	cout << solve () << endl;
	//Output region
	#ifdef RLAC
		cout << flush;
		clog << clock() - TIME << endl;
		fclose(FILE_NAME);
		system("notepad "NAME".out");
	#endif
	return 0;
}

Judgement Details

Test 01: 0.018 0.016 1468K ok
Test 02: 0.010 0.016 1472K ok
Test 03: 0.010 0.000 1476K ok
Test 04: 0.012 0.016 1864K ok
Test 05: 0.088 0.094 4984K ok
Test 06: 0.009 0.000 1856K ok
Test 07: 0.011 0.016 1860K ok
Test 08: 0.010 0.000 1860K ok
Test 09: 0.124 0.094 4956K ok
Test 10: 0.044 0.047 1820K ok
Test 11: 0.010 0.000 1468K ok
Test 12: 0.011 0.000 1476K ok
Test 13: 0.010 0.000 1468K ok
Test 14: 0.039 0.031 2172K ok
Test 15: 0.032 0.016 2736K ok
Test 16: 0.011 0.000 1696K ok
Test 17: 0.010 0.000 1672K ok
Test 18: 0.011 0.016 1800K ok
Test 19: 0.024 0.016 2100K ok
Test 20: 0.079 0.078 4444K ok
Test 21: 0.009 0.000 1844K ok
Test 22: 0.010 0.000 1468K ok
Test 23: 0.030 0.016 2416K ok
Test 24: 0.011 0.000 1604K ok
Test 25: 0.009 0.000 1776K ok
Test 26: 0.010 0.000 1800K ok
Test 27: 0.011 0.000 1696K ok
Test 28: 0.009 0.000 1700K ok
Test 29: 0.009 0.000 1736K ok
Test 30: 0.055 0.016 2844K ok
Test 31: 0.089 0.078 4860K ok
Test 32: 0.012 0.000 1748K ok
Test 33: 0.010 0.000 1544K ok
Test 34: 0.009 0.000 1844K ok
Test 35: 0.038 0.016 2736K ok
Test 36: 0.016 0.016 1836K ok
Test 37: 0.010 0.000 1732K ok
Test 38: 0.012 0.000 1624K ok
Test 39: 0.008 0.000 1528K ok
Test 40: 0.021 0.016 2388K ok
Test 41: 0.030 0.031 2492K ok
Test 42: 0.009 0.000 1588K ok
Test 43: 0.011 0.000 1728K ok
Test 44: 0.080 0.062 4540K ok
Test 45: 0.009 0.000 1496K ok
Test 46: 0.008 0.000 1544K ok
Test 47: 0.045 0.031 2620K ok
Test 48: 0.010 0.000 1864K ok
Test 49: 0.039 0.016 3196K ok
Test 50: 0.017 0.016 1776K ok
Test 51: 0.073 0.047 4088K ok
Test 52: 0.009 0.000 1856K ok
Test 53: 0.064 0.062 3676K ok
Test 54: 0.009 0.000 1536K ok
Test 55: 0.032 0.031 1884K ok
Test 56: 0.018 0.000 2004K ok
Test 57: 0.018 0.016 2036K ok
Test 58: 0.010 0.000 1776K ok
Test 59: 0.014 0.000 2032K ok
Test 60: 0.011 0.000 1720K ok
Test 61: 0.009 0.000 1660K ok
Test 62: 0.023 0.016 2588K ok
Test 63: 0.039 0.031 2268K ok
Test 64: 0.010 0.000 1640K ok
Test 65: 0.009 0.000 1672K ok
Accepted

Matcom Online Grader