Submission #3744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3744	2013-08-31T08:03:54 Z	Apple_Cplus	Block stacker (kriii1_B)	C++	1 / 1	284 ms	2656 KB

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2656 KB	Output is correct
2	Correct	0 ms	2656 KB	Output is correct
3	Correct	0 ms	2656 KB	Output is correct
4	Correct	0 ms	2656 KB	Output is correct
5	Correct	0 ms	2656 KB	Output is correct
6	Correct	0 ms	2656 KB	Output is correct
7	Correct	4 ms	2656 KB	Output is correct
8	Correct	8 ms	2656 KB	Output is correct
9	Correct	8 ms	2656 KB	Output is correct
10	Correct	8 ms	2656 KB	Output is correct
11	Correct	48 ms	2656 KB	Output is correct
12	Correct	40 ms	2656 KB	Output is correct
13	Correct	28 ms	2656 KB	Output is correct
14	Correct	52 ms	2656 KB	Output is correct
15	Correct	16 ms	2656 KB	Output is correct
16	Correct	176 ms	2656 KB	Output is correct
17	Correct	240 ms	2656 KB	Output is correct
18	Correct	280 ms	2656 KB	Output is correct
19	Correct	272 ms	2656 KB	Output is correct
20	Correct	284 ms	2656 KB	Output is correct