Submission #401002

#	Time	Username	Problem	Language	Result	Execution time	Memory
401002		gaurav172	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	371 ms	160268 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const int M = 101;
const int mod = 1e9+7;
int a[M],n,L;
int dp[101][1001][2][101][2];

int solve(int id, int l, int kl, int k, int kr)
{
	int nl = l;
	if(id > 1)
	{
		nl += (kl + kr + 2*k)*(a[id] - a[id-1]);
	}
	if(nl > L)
		return 0;

	if(id == n)
	{
		if(k)
			return 0;
		else
			return 1;
	}

	if(dp[id][l][kl][k][kr] != -1)
		return dp[id][l][kl][k][kr];
	
	int res = 0;

	// add to the left segment
	res = (res + solve(id + 1, nl, 1, k, kr))%mod;
	// add to left and merge with middle
	if(k)
		res = (res + (k*1LL*solve(id + 1, nl, 1, k - 1, kr))%mod)%mod;

	// add to the right segment
	res = (res + solve(id + 1, nl, kl, k, 1))%mod;
	// add to right and merge with middle
	if(k)
		res = (res + (k*1LL*solve(id + 1, nl, kl, k - 1, 1))%mod)%mod;

	// create new in the middle
	res = (res + solve(id + 1, nl, kl , k + 1, kr))%mod;

	// add to some segment in the middle
	if(k)
		res = (res + (k*2LL*solve(id + 1, nl, kl, k, kr))%mod)%mod;

	// merge two middle segments
	if(k >= 2)
		res = (res + (k*(k-1)*1LL*solve(id + 1, nl, kl, k-1, kr))%mod)%mod;

	return dp[id][l][kl][k][kr] = res;
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>L;

	for(int i=1;i<=n;i++)
		cin>>a[i];

	sort(a+1, a+n+1);
	memset(dp, -1, sizeof(dp));
	cout<<solve(1, 0, 0, 0, 0)<<"\n";
	return 0;
}

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