Submission #44672

#	Time	Username	Problem	Language	Result	Execution time	Memory
44672		IvanC	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	401 ms	321228 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXL = 1002;
const int MAXN = 101;
const ll MOD = 1e9 + 7;
ll dp[MAXN][MAXN][2][2][MAXL],N,L,V[MAXN];
ll solve(ll pos,ll cmp,ll lcmp,ll rcmp,ll penalty){
	if(cmp < 0) return 0;
	if(dp[pos][cmp][lcmp][rcmp][penalty] != -1) return dp[pos][cmp][lcmp][rcmp][penalty]; 
	ll penalty_now = penalty;
	if(pos > 1) penalty_now += (2*cmp + lcmp + rcmp)*abs(V[pos] - V[pos-1]);
	if(penalty_now > L) return dp[pos][cmp][lcmp][rcmp][penalty] = 0;
	if(pos == N){
		if(cmp == 0) return dp[pos][cmp][lcmp][rcmp][penalty] = 1;
		else return dp[pos][cmp][lcmp][rcmp][penalty] = 0;
	}
	ll tot = 0;
	tot += solve(pos+1,cmp,1,rcmp,penalty_now);
	tot += solve(pos+1,cmp-1,1,rcmp,penalty_now)*cmp;
	tot += solve(pos+1,cmp,lcmp,1,penalty_now);
	tot += solve(pos+1,cmp-1,lcmp,1,penalty_now)*cmp;
	tot += solve(pos+1,cmp,lcmp,rcmp,penalty_now)*(2*cmp);
	tot += solve(pos+1,cmp+1,lcmp,rcmp,penalty_now);
	tot += solve(pos+1,cmp-1,lcmp,rcmp,penalty_now)*cmp*(cmp-1);
	return dp[pos][cmp][lcmp][rcmp][penalty] = (tot % MOD);
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin >> N >> L;
	for(int i = 1;i<=N;i++) cin >> V[i];
	sort(V+1,V+N+1);
	cout << solve(1,0,0,0,0) << endl;
	return 0;
}

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