oj.uz

답안 #51171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51171 2018-06-17T03:52:27 Z spencercompton Skyscraper (JOI16_skyscraper) C++17
15 / 100
 289 ms 317264 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;
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 289 ms 316880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 226 ms 316948 KB Output is correct
2 Correct 236 ms 316964 KB Output is correct
3 Correct 225 ms 316964 KB Output is correct
4 Correct 234 ms 317188 KB Output is correct
5 Correct 256 ms 317188 KB Output is correct
6 Correct 233 ms 317188 KB Output is correct
7 Correct 224 ms 317188 KB Output is correct
8 Correct 223 ms 317264 KB Output is correct
9 Correct 228 ms 317264 KB Output is correct
10 Correct 217 ms 317264 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 289 ms 316880 KB Output isn't correct
2 Halted 0 ms 0 KB -