Submission #681960

#	Time	Username	Problem	Language	Result	Execution time	Memory
681960		vjudge1	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	59 ms	130380 KiB

skyscraper

///****In the name of ALLAH, most Gracious, most Compassionate****//

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define ALL(a) a.begin(), a.end()
#define FastIO ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define IN freopen("input.txt","r+",stdin)
#define OUT freopen("output.txt","w+",stdout)

#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define NL cerr<<endl

template < class T1,class T2>
ostream &operator <<(ostream &os,const pair < T1,T2 > &p)
{
    os<<"{"<<p.first<<","<<p.second<<"}";
    return os;
}
template <class T , size_t N>
ostream &operator <<(ostream &os,const array <T,N> &a)
{
	os<<"{";
	for(auto x: a)
		os<<x<<" ";
	os<<"}";
	return os;
}

template <class T>
ostream &operator <<(ostream &os,const vector<T> &a)
{
	os<<"{ ";
	for(auto x: a)
		os<<x<<" ";
	os<<"}";
	return os;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N=100+5;
const int M=1e3+5;
const ll oo=1e9+7;

int a[N];
int n,l;
int save[N][N][M][3];
int dp(int i,int cc,int sm,ll side)
{
	
	// DBG(i);
	// DBG(cc);
	// DBG(sm);
	// DBG(side);
	// DBG(side == 2 and cc == 1);
	// NL;
	assert(cc>=0);
	if(sm>l) return 0;
	if(i==n+1) return side == 2 and cc == 1;
	int &ret = save[i][cc][sm][side];
	if(ret!=-1) return ret;
	ret= 0;
	int d =a[i]-a[i-1];
	int nxt = sm + d* (2*cc-side);

	// new comp
	{
		ret = (ret + dp(i+1,cc+1,nxt,side)*1LL*(cc+1 - side))%oo;
	}

	// merge
	if(cc>=2)
	{
		ret =(ret + dp(i+1,cc-1,nxt,side) * 1LL * (cc-1))%oo;
	}
	// add
	if(2*cc-side>=1)
	{
		ret = (ret + dp(i+1,cc,nxt,side)* 1LL * (2*cc-side)	)%oo;
	}

	if(side <2)
	{
		ret = (ret +dp(i+1,cc+1,nxt,side +1 ) * (2-side))%oo;
		// if(cc==0)
		// 	ret = (ret +dp(i+1,cc+1,nxt,side +2 ) * (1))%oo;

		ret = (ret +dp(i+1,cc,nxt,side +1 ) * (2-side))%oo;
	}


	return ret;
}


int32_t main()
{
    FastIO;
	cin>>n>>l;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	if(n==1)
	{
		cout<<"1\n";
		return 0;
	}
	// a[0]=a[1];
	// DBG(a);
	// for(int i=1;i<=n;i++) cerr<<a[i]<<" ";
	// NL;

	// for(int i=1;i<=n;i++)
	// {
	// 	DBG(i);
	// 	DBG(dp(i,0,0,0));
	// 	NL;
	// }
	memset(save,-1,sizeof save);
	cout<<dp(1,0,0,0)<<"\n";
}

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