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
#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;
}
# 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 -