Submission #728590

#	Time	Username	Problem	Language	Result	Execution time	Memory
728590		vjudge1	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	2 ms	1620 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const ll MOD=1e9+7;
ll N,M,a[105],dp[105][105][1005][3];
int main(){
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	sort(a+1,a+N+1);
	a[0]=0;
	dp[0][0][0][0]=1;
	for(int i=0;i<=N-1;i++){
		for(int cc=0;cc<=N;cc++){
			for(int k=0;k<=M;k++){
				for(int e=0;e<=2;e++){
					if(2*cc-e<0){
						continue;
					}
					ll cost=(a[i+1]-a[i])*(2*cc-e);
					if(k+cost>M){
						continue;
					}
					ll cur=dp[i][cc][k][e];
					//new
					dp[i+1][cc+1][k+cost][e]+=cur;
					if(e<=1){
						dp[i+1][cc+1][k+cost][e+1]+=(2-e)*cur;
					}
					//stick
					dp[i+1][cc][k+cost][e]+=(2*cc-e)*cur;
					dp[i+1][cc][k+cost][e+1]+=(2-e)*(cc-e)*cur;
					if(i==N-1){
						dp[i+1][cc][k+cost][e+1]+=cur;
					}
					//merge
					if(cc-e>=2){
						dp[i+1][cc-1][k+cost][e]+=(cc-e)*(cc-e-1)*cur;
					}
					if(cc-e>0&&e>0){
						dp[i+1][cc-1][k+cost][e]+=(cc-e)*e*cur;
					}
					if(e==2&&i==N-1){
						dp[i+1][cc-1][k+cost][e]+=cur;
					}
					dp[i+1][cc+1][k+cost][e]%=MOD;
					dp[i+1][cc+1][k+cost][e+1]%=MOD;
					dp[i+1][cc][k+cost][e]%=MOD;
					dp[i+1][cc][k+cost][e+1]%=MOD;
					dp[i+1][cc-1][k+cost][e]%=MOD;
				}
			}
		}
	}
	ll sum=0;
	for(int i=0;i<=M;i++){
		sum+=dp[N][1][i][2];
		sum%=MOD;
	}
	cout<<sum<<endl;
}

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