Submission #51172

#	Time	Username	Problem	Language	Result	Execution time	Memory
51172		spencercompton	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	1016 ms	317432 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[2][2][100][101][1001];
ll mod = 1000000007LL;
int n;
int ar[100];
ll go(int f, int e, int now, int blocks, int rem){
	if(now==n){
		if(f==1 && e==1 && blocks==1 && rem>=0){
			return 1LL;
		}
		return 0LL;
	}
	if(blocks<0){
		return 0LL;
	}
	int open = 2*blocks - f - e;
	if(now>0){
		rem -= open * (ar[now]-ar[now-1]);
	}
	if(rem<0){
		return 0LL;
	}
	if(dp[f][e][now][blocks][rem]!=-1LL){
		return dp[f][e][now][blocks][rem];
	}
	ll ret = 0LL;
	if(f==1 && e==1){
		//make new block
		ret += go(f,e,now+1,blocks+1,rem);

		//combine two blocks:
		ret %= mod;
		//f first e second
		if(now==n-1){
			ret += go(f,e,now+1,blocks-1,rem);
			ret %= mod;
		}
		
		if(blocks>2){
			//f first something else second
			ret += go(f,e,now+1,blocks-1,rem)*(blocks-2);
			//something first e second
			ret %= mod;
			ret += go(f,e,now+1,blocks-1,rem)*(blocks-2);
			ret %= mod;
		}
		if(blocks>3){
			//something first something second
			ret += go(f,e,now+1,blocks-1,rem) * (blocks-2) * (blocks-3);
			ret %= mod;
		}

		//add to begin of block
		ret += go(f,e,now+1,blocks,rem) * (blocks-1);
			ret %= mod;

		//add to end of block
		ret += go(f,e,now+1,blocks,rem) * (blocks-1);
			ret %= mod;
	}
	else if(f==1 && e==0){
		//make new block
		ret += go(f,e,now+1,blocks+1,rem);
		//that is end
			ret %= mod;
		ret += go(f,1,now+1,blocks+1,rem);
			ret %= mod;
		//combine two blocks:
		
		if(blocks>1){
			//f first something else second
			ret += go(f,e,now+1,blocks-1,rem)*(blocks-1);
			ret %= mod;
		}
		if(blocks>2){
			//something first something second
			ret += go(f,e,now+1,blocks-1,rem) * (((blocks-1) * (blocks-2))%mod);
			ret %= mod;
		}

		//add to begin of block
		ret += go(f,e,now+1,blocks,rem) * (blocks-1);
			ret %= mod;

		//add to end of block
		ret += go(f,e,now+1,blocks,rem) * (blocks);
			ret %= mod;
		//and make it the end
		if(now==n-1){
			ret += go(f,1,now+1,blocks,rem);
			ret %= mod;
		}
		else if(blocks>1) {
			ret += go(f,1,now+1,blocks,rem)*(blocks-1);
			ret %= mod;
		}
	}
	else if(f==0 && e==1){
		//make new block
		ret += go(f,e,now+1,blocks+1,rem);
			ret %= mod;
		//that it begin
		ret += go(1,e,now+1,blocks+1,rem);
			ret %= mod;
		//combine two blocks:
		
		if(blocks>1){
			//something first e second
			ret += go(f,e,now+1,blocks-1,rem)*(blocks-1);
			ret %= mod;
		}
		if(blocks>2){
			//something first something second
			ret += go(f,e,now+1,blocks-1,rem) * (((blocks-1) * (blocks-2))%mod);
			ret %= mod;
		}

		//add to begin of block
		ret += go(f,e,now+1,blocks,rem) * (blocks);
			ret %= mod;
		//and make it begin
		if(now==n-1){
			ret += go(1,e,now+1,blocks,rem);
			ret %= mod;
		}
		else if(blocks>1){
			ret += go(1,e,now+1,blocks,rem)*(blocks-1);
			ret %= mod;
		}
		//add to end of block
		ret += go(f,e,now+1,blocks,rem) * (blocks-1);
			ret %= mod;
	}
	else if(f==0 && e==0){
		//make new block
		ret += go(f,e,now+1,blocks+1,rem);
			ret %= mod;
		//that is end
		ret += go(f,1,now+1,blocks+1,rem);
			ret %= mod;
		//that is begin
		ret += go(1,e,now+1,blocks+1,rem);
			ret %= mod;
		//combine two blocks:
		if(blocks>1){
			//something first something second
			ret += go(f,e,now+1,blocks-1,rem) * (((blocks) * (blocks-1))%mod);
			ret %= mod;
		}

		//add to begin of block
		ret += go(f,e,now+1,blocks,rem) * (blocks);
			ret %= mod;
		//and make it begin
		ret += go(1,e,now+1,blocks,rem) * blocks;
			ret %= mod;
		//add to end of block
		ret += go(f,e,now+1,blocks,rem) * (blocks);
			ret %= mod;
		//and make it end
		ret += go(f,1,now+1,blocks,rem) * blocks;
			ret %= mod;
	}
	else{
		assert(false);
	}
	dp[f][e][now][blocks][rem] = ret;
	return ret;
}
/*

ll dp[2][2][100][101][1001];
int n
ll l
*/
int main(){
	int l;
	cin >> n >> l;
	if(n==1){
		cout << 1 << endl;
		return 0LL;
	}
	for(int i = 0; i<n; i++){
		cin >> ar[i];
	}
	sort(ar,ar+n);
	for(int a = 0; a<2; a++){
		for(int b =0; b<2; b++){
			for(int c = 0; c<100; c++){
				for(int d = 0; d<=100; d++){
					for(int e = 0; e<=1000; e++){
						dp[a][b][c][d][e] = -1LL;
					}
				}
			}
		}
	}
	cout << go(0,0,0,0,l);
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80