제출 #598022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598022		CSQ31	Skyscraper (JOI16_skyscraper)	C++17	0 / 100	2 ms	3028 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int a[101];
//number of cc,current cost , whether left side is chosen whether right is chosen 
//index of element we are considering
const int MOD = 1e9+7;
int mult(int a,int b){
	return a*1LL*b%MOD;
}
inline void add(int &a,int b){
	a+=b;
	if(a>=MOD)a-=MOD;
}
int dp[2][2][101][101][1001],n,L;
int solve(int lf,int rg,int i,int cnt,int cost){ //#total if we start from this state
	if(cost>L || cnt<0)return 0;
	if(dp[lf][rg][i][cnt][cost] != -1)return dp[lf][rg][i][cnt][cost];
	if(i==n){ //base case
		if(cnt==1 && lf && rg)return 1;
		else return 0;
	}
	//once left and right border are made,no changes can be done to them :check
	//no this fails
	//new rule left and right border must start off as single cell
	int d = a[i+1]-a[i];
	dp[lf][rg][i][cnt][cost] = 0;
	int nwcost = cost + (2*cnt - lf - rg) * d; //cost assuming every open end continues being open
	//1)
	//make single new cc
	add(dp[lf][rg][i][cnt][cost],solve(lf,rg,i+1,cnt+1,nwcost + 2*d)); 
	//make single new left cc
	if(!lf)add(dp[lf][rg][i][cnt][cost],solve(1,rg,i+1,cnt+1,nwcost + d)); 
	//make single new right cc
	if(!rg)add(dp[lf][rg][i][cnt][cost],solve(lf,1,i+1,cnt+1,nwcost + d)); 
	
	//2)
	//connect to left side of smtg
	if(cnt-lf)add(dp[lf][rg][i][cnt][cost],mult(cnt-lf,solve(lf,rg,i+1,cnt,nwcost)));
	//connect to right side of smtg
	if(cnt-rg)add(dp[lf][rg][i][cnt][cost],mult(cnt-rg,solve(lf,rg,i+1,cnt,nwcost)));
	//make single left then connect smtg
	if(!lf && cnt-rg)add(dp[lf][rg][i][cnt][cost],mult(cnt-rg,solve(1,rg,i+1,cnt,nwcost-d)));
	//make single right then connect smtg
	if(!rg && cnt-lf)add(dp[lf][rg][i][cnt][cost],mult(cnt-lf,solve(lf,1,i+1,cnt,nwcost-d)));
	
	//3)
	//merge ccs
	int cc = cnt-lf-rg;
	if(cc>=2)add(dp[lf][rg][i][cnt][cost],mult(cc*(cc+1)/2,solve(lf,rg,i+1,cnt-1,nwcost - 2*d)));
	if(cc && lf)add(dp[lf][rg][i][cnt][cost],mult(cc,solve(lf,rg,i+1,cnt-1,nwcost - 2*d)));
	if(cc && rg)add(dp[lf][rg][i][cnt][cost],mult(cc,solve(lf,rg,i+1,cnt-1,nwcost - 2*d)));
	

	//merge left and right border
	//only possible in enddgame
	//4)
	if(i==n-1){
		if(lf && rg)add(dp[lf][rg][i][cnt][cost],solve(1,1,n,cnt-1,nwcost - 2*d));
		if(lf && !rg)add(dp[lf][rg][i][cnt][cost],solve(1,1,n,cnt,nwcost)); //connect to left side
		if(!lf && rg)add(dp[lf][rg][i][cnt][cost],solve(1,1,n,cnt,nwcost)); //connected to right side
	}
	cout<<dp[lf][rg][i][cnt][cost]<<'\n';
	return dp[lf][rg][i][cnt][cost];
}
int main()
{
	cin>>n>>L;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	a[n] = a[n-1];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=L;k++){
				for(int mask=0;mask<=3;mask++){
					dp[mask&1][mask/2][i][j][k] = -1;
					
				}
			}
			
		}
	}
	cout<<solve(0,0,0,0,0);
	
}

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