oj.uz

Submission #51172

# Submission time Handle Problem Language Result Execution time Memory
51172 2018-06-17T03:53:29 Z spencercompton Skyscraper (JOI16_skyscraper) C++17
100 / 100
 1016 ms 317432 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 219 ms 317032 KB Output is correct
3 Correct 220 ms 317060 KB Output is correct
4 Correct 238 ms 317060 KB Output is correct
5 Correct 221 ms 317160 KB Output is correct
6 Correct 234 ms 317244 KB Output is correct
7 Correct 217 ms 317244 KB Output is correct
8 Correct 217 ms 317244 KB Output is correct
9 Correct 237 ms 317244 KB Output is correct
10 Correct 221 ms 317244 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 317244 KB Output is correct
2 Correct 223 ms 317244 KB Output is correct
3 Correct 243 ms 317244 KB Output is correct
4 Correct 224 ms 317244 KB Output is correct
5 Correct 227 ms 317244 KB Output is correct
6 Correct 229 ms 317244 KB Output is correct
7 Correct 227 ms 317244 KB Output is correct
8 Correct 218 ms 317244 KB Output is correct
9 Correct 224 ms 317284 KB Output is correct
10 Correct 225 ms 317284 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 219 ms 317032 KB Output is correct
3 Correct 220 ms 317060 KB Output is correct
4 Correct 238 ms 317060 KB Output is correct
5 Correct 221 ms 317160 KB Output is correct
6 Correct 234 ms 317244 KB Output is correct
7 Correct 217 ms 317244 KB Output is correct
8 Correct 217 ms 317244 KB Output is correct
9 Correct 237 ms 317244 KB Output is correct
10 Correct 221 ms 317244 KB Output is correct
11 Correct 228 ms 317244 KB Output is correct
12 Correct 223 ms 317244 KB Output is correct
13 Correct 243 ms 317244 KB Output is correct
14 Correct 224 ms 317244 KB Output is correct
15 Correct 227 ms 317244 KB Output is correct
16 Correct 229 ms 317244 KB Output is correct
17 Correct 227 ms 317244 KB Output is correct
18 Correct 218 ms 317244 KB Output is correct
19 Correct 224 ms 317284 KB Output is correct
20 Correct 225 ms 317284 KB Output is correct
21 Correct 224 ms 317284 KB Output is correct
22 Correct 978 ms 317336 KB Output is correct
23 Correct 685 ms 317336 KB Output is correct
24 Correct 940 ms 317336 KB Output is correct
25 Correct 698 ms 317336 KB Output is correct
26 Correct 702 ms 317336 KB Output is correct
27 Correct 437 ms 317336 KB Output is correct
28 Correct 489 ms 317336 KB Output is correct
29 Correct 1016 ms 317428 KB Output is correct
30 Correct 624 ms 317432 KB Output is correct