Submission #3765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3765	2013-08-31T08:14:18 Z	blmarket	Block stacker (kriii1_B)	C++	1 / 1	588 ms	3136 KB

B

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

int K,W,H;
map<int, VI> cs;
VVI bs;
long long nmet[305][305];
long long nm[305];
long long mod = 1000000007LL;

long long memo[305][305];

long long go(int a, int b) {
    // cout << a << " " << b << endl;
    if(a == 0) return 1;
    if(b <= 0) return 1;
    if(memo[a][b] != -1) return memo[a][b];

    long long ret = go(a, b-1);
    for(int i=1;i<=b;i++) {
        long long tmp = nm[i] * go(a-1, i);
        tmp %= mod;
        ret += tmp * go(a, b-i-1);
        ret %= mod;
    }
    return memo[a][b] = ret;
}

int main(void)
{
    memset(memo, -1, sizeof(memo));
    cin >> K >> W >> H;
    for(int i=0;i<K;i++) {
        int a;
        cin >> a;
        cs[a].pb(i+1);
    }

    foreach(it, cs) {
        VI &cur = it->second;
        bool avail[605];
        memset(avail, 0, sizeof(avail));
        avail[0] = true;
        for(int i=0;i<W;i++) if(avail[i]) {
            for(int j=0;j<size(cur);j++) {
                avail[i+cur[j]] = true;
            }
        }
        bs.pb(VI());
        for(int i=1;i<=W;i++) if(avail[i]) {
            bs.back().pb(i);
        }
    }

    memset(nmet, 0, sizeof(nmet));
    nmet[0][0] = 1;
    for(int i=0;i<=W;i++) {
        for(int j=0;j<size(bs);j++) {
            long long ns = 0;
            for(int k=0;k<size(bs);k++) if(j!=k || i==0) {
                ns += nmet[i][k];
                if(ns >= mod) ns -= mod;
            }
            if(ns == 0) continue;

            VI &avail = bs[j];
            for(int k=0;k<size(avail);k++) {
                if(i + avail[k] > W) break;
                nmet[i+avail[k]][j] += ns;
                if(nmet[i+avail[k]][j] >= mod)
                    nmet[i+avail[k]][j] -= mod;
            }
        }

        nm[i] = 0;
        for(int j=0;j<size(bs);j++) {
            nm[i] += nmet[i][j];
        }
        nm[i] %= mod;
    }

    cout << go(H, W) << endl;
    return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3136 KB	Output is correct
2	Correct	0 ms	3136 KB	Output is correct
3	Correct	0 ms	3136 KB	Output is correct
4	Correct	4 ms	3136 KB	Output is correct
5	Correct	0 ms	3136 KB	Output is correct
6	Correct	4 ms	3136 KB	Output is correct
7	Correct	12 ms	3136 KB	Output is correct
8	Correct	16 ms	3136 KB	Output is correct
9	Correct	16 ms	3136 KB	Output is correct
10	Correct	12 ms	3136 KB	Output is correct
11	Correct	100 ms	3136 KB	Output is correct
12	Correct	88 ms	3136 KB	Output is correct
13	Correct	56 ms	3136 KB	Output is correct
14	Correct	100 ms	3136 KB	Output is correct
15	Correct	32 ms	3136 KB	Output is correct
16	Correct	356 ms	3136 KB	Output is correct
17	Correct	500 ms	3136 KB	Output is correct
18	Correct	560 ms	3136 KB	Output is correct
19	Correct	580 ms	3136 KB	Output is correct
20	Correct	588 ms	3136 KB	Output is correct