Submission #3744

#	Time	Username	Problem	Language	Result	Execution time	Memory
3744		Apple_Cplus	Block stacker (kriii1_B)	C++98	1 / 1	284 ms	2656 KiB

B

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
 
using namespace std;

#define MOD 1000000007ll
#define ll long long

int K,w,h;
int C[333];

vector<int> bar[333];

bool can[333][333]; // clr_num, len
int d1[333][333]; // len, last
int sum[333];

int d2[333][333];
int go(int len, int ht) {
	if(len < 0) return 1;
	if(ht > h) return 1;

	int &ret = d2[len][ht];
	if(ret != -1) return ret;
	ret = 0;
	ret = (ret + go(len-1,ht)) % MOD;
	//ret = (ret + d1[len] * go(len,ht+1) % MOD) %MOD;
	for(int l2=1;l2<=len;++l2) {
		ret = (ret + (ll)go(len-l2-1,ht) * sum[l2] % MOD * go(l2,ht+1) % MOD) % MOD;
	} return ret;
}


int main() {
	scanf("%d%d%d",&K,&w,&h);
	for(int i=1;i<=K;++i) scanf("%d",C+i);

	for(int i=1;i<=K;++i) bar[C[i]].push_back(i);
	for(int i=1;i<=K;++i) { // i : clr_num
		can[i][0] = 1;
		for(int j=0;j<bar[i].size();++j)
		for(int k=0;k<=w;++k) if(k+bar[i][j]<=w) {
			can[i][k+bar[i][j]] |= can[i][k];
		}
	}

	sum[0] = 1;
	for(int i=1;i<=w;++i) {
		for(int c=1;c<=K;++c) {
			for(int k=1;k<=i;++k) if(can[c][k]) {
				d1[i][c] = ((d1[i][c] + sum[i-k]) % MOD - d1[i-k][c] + MOD) % MOD;
			}
			sum[i] = (sum[i] + d1[i][c]) % MOD;
		}
	}
	memset(d2,-1,sizeof(d2));
	printf("%d",go(w,1));
}

• Subtask 1: 1 / 1