Submission #3765

#	Time	Username	Problem	Language	Result	Execution time	Memory
3765		blmarket	Block stacker (kriii1_B)	C++98	1 / 1	588 ms	3136 KiB

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 / 1