oj.uz

Submission #51170

# Submission time Handle Problem Language Result Execution time Memory
51170 2018-06-17T03:48:27 Z spencercompton Skyscraper (JOI16_skyscraper) C++17
0 / 100
 276 ms 317268 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:

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

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

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

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

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

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

		//add to begin of block
		ret += go(f,e,now+1,blocks,rem) * (blocks);
		//and make it begin
		ret += go(1,e,now+1,blocks,rem) * blocks;
		//add to end of block
		ret += go(f,e,now+1,blocks,rem) * (blocks);
		//and make it end
		ret += go(f,1,now+1,blocks,rem) * blocks;
	}
	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;
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 316880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 317028 KB Output is correct
2 Correct 276 ms 317028 KB Output is correct
3 Correct 239 ms 317268 KB Output is correct
4 Correct 218 ms 317268 KB Output is correct
5 Correct 240 ms 317268 KB Output is correct
6 Correct 230 ms 317268 KB Output is correct
7 Correct 258 ms 317268 KB Output is correct
8 Correct 233 ms 317268 KB Output is correct
9 Incorrect 224 ms 317268 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 316880 KB Output isn't correct
2 Halted 0 ms 0 KB -