MOG
Spanish
|
English

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
​x
 
1
#include <algorithm>
2
#include <cstdio>
3
#include <cstdlib>
4
#include <cstring>
5
#include <ctime>
6
#include <iostream>
7
#include <vector>
8
​
9
#ifdef RLAC
10
    #define DEB(a)          clog << __LINE__ << ": " << #a << " = " << (a) << endl
11
    #define OUT(a, n)       for (int J = 0; J < (n); ++J)   clog << (a)[J] << " \n"[J == (n) - 1];
12
    #define NAME            "E"
13
#else
14
    #define DEB(a)
15
    #define OUT(a, n)
16
#endif
17
​
18
using namespace std;
19
​
20
const int MAXN = 12, MAXM = 105, MOD = 1e9 + 7;
21
typedef long long ll;
22
​
23
vector<int> d[1 << MAXN];   /* d[msk] contiene las máscaras que son compatibles con msk.    */
24
ll dp[MAXM + 2][1 << MAXN];
25
int n, m;
26
​
27
/*  Computa la tabla d  */
28
void go (int p, int p2, int l)
29
{
30
    if (l == n)
31
        d[p2].push_back(p);
32
    else if ((1 << l) & p)
33
        go(p, p2, l + 1);                               /*  La l-ésima casilla está ocupada, continua a la próxima  */
34
    else
35
    {
36
        go(p, p2 | (1 << l), l + 1);                    /*  Pone una ficha de dominó horizontal.    */
37
38
        if (l < n - 1 && ((1 << (l + 1)) & p) == 0)     /*  Ni la l-ésima ni la (l + 1)-ésima casilla están ocupadas.   */
39
            go(p, p2, l + 2);                           /*  Pone una ficha vertical (esto no afecta la siguiente columna) */
40
    }
41
}
42
​
43
ll solve ()
44
{
45
    for (int i = 0; i < (1 << n); ++i)
46
        go (i, 0, 0);
47
48
    dp[1][0] = 1;
49
​
50
    for (int i = 2; i <= m + 1; ++i)
51
    {
52
        for (int msk = 0; msk < (1 << n); ++msk)
53
        {
54
            for (int j = 0; j < d[msk].size(); ++j)     /* Se recorren las máscaras que son compatibleas con msk    */
55
            {
56
                dp[i][msk] = (dp[i][msk] + dp[i - 1][d[msk][j]]) % MOD;
57
            }
58
        }
59
    }
60
​
61
    return dp[m + 1][0];
62
}
63
​
64
int main ()
65
{
66
    //Improvement region
67
    ios_base::sync_with_stdio(0);
68
    cin.tie(0);
69
​
70
    //Input region
71
    #ifdef RLAC
72
        system("notepad "NAME".in");
73
        freopen(NAME".in", "r", stdin);
74
        FILE * FILE_NAME = freopen(NAME".out", "w", stdout);
75
        int TIME = clock();
76
    #endif
77
    //Add your code here...
78
    cin >> n >> m;
79
    cout << solve () << endl;
80
    //Output region
81
    #ifdef RLAC
82
        cout << flush;
83
        clog << clock() - TIME << endl;
84
        fclose(FILE_NAME);
85
        system("notepad "NAME".out");
86
    #endif
87
    return 0;
88
}
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