Submission #3748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3748	2013-08-31T08:05:26 Z	blmarket	Block stacker (kriii1_B)	C++	0 / 1	20 ms	2540 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;

map<PII, long long> memo;

long long go(int a, int b) {
    // cout << a << " " << b << endl;
    if(a == 0) return 1;
    if(b <= 0) return 1;
    PII key = mp(a,b);
    if(memo.count(key)) return memo[key];

    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[key] = ret;
}

int main(void)
{
    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 == 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;
            }
        }

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

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

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2408 KB	Output is correct
2	Correct	0 ms	2408 KB	Output is correct
3	Incorrect	20 ms	2540 KB	Output isn't correct
4	Halted	0 ms	0 KB	-