Submission #598130

#	Time	Username	Problem	Language	Result	Execution time	Memory
598130		CSQ31	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	242 ms	320108 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int a[101];
typedef long long int ll;
const int MOD = 1e9+7;
ll dp[2][2][101][101][1001],n,L;
//left border chosen?
//right border chosen?
//we are currently deciding where is i
//there are cnt comps
//total cost right now is cost
ll solve(int lf,int rg,int i,int cnt,int cost){
	 //#total if we start from this state
	if(cnt<0)return 0;
	if(dp[lf][rg][i][cnt][cost] != -1)return dp[lf][rg][i][cnt][cost];
	//replace everyt "?" with a[i]
	int ocost = cost;
	if(i)cost+=(2*cnt + lf + rg) * (a[i]-a[i-1]);
	if(cost > L )return 0;
	if(i==n-1)return cnt == 0;	
	ll res = 0;
	res += solve(lf,rg,i+1,cnt+1,cost); //single comp  b i b 
    res += solve(lf,rg,i+1,cnt,cost) * (cnt+lf); //attach to right side of smtg s i b
    res += solve(lf,rg,i+1,cnt,cost) * (cnt+rg); //attach to left side of smtg b i s
    if(!lf){
		res += solve(1,rg,i+1,cnt,cost); //make you left border
		res += solve(1,rg,i+1,cnt-1,cost)*cnt; //and also merge with smtg
	}
    if(!rg){
		res += solve(lf,1,i+1,cnt,cost); //make you right border 
		res += solve(lf,1,i+1,cnt-1,cost) * cnt; //and also merge with smtg
	}
    
    if(lf && cnt)res += solve(lf,rg,i+1,cnt-1,cost) * cnt;  //merge smtg with left border
    if(rg && cnt)res += solve(lf,rg,i+1,cnt-1,cost) * cnt;  //merge smtg with right border
    if(cnt>1) res += solve(lf,rg,i+1,cnt-1,cost) * cnt*(cnt-1); //s i s //merge two non border guys
    res%=MOD;
    return dp[lf][rg][i][cnt][ocost] = res%MOD;
    
}
int main()
{
	cin>>n>>L;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	memset(dp,-1,sizeof(dp));
	cout<<solve(0,0,0,0,0);
	
}

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