Submission #329737

#	Time	Username	Problem	Language	Result	Execution time	Memory
329737		GioChkhaidze	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	340 ms	5228 KiB

skyscraper

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=103;
const int L=1004;

ll mod=1e9+7;
ll dp[N][L][3];
ll dp_[N][L][3];
ll n,l,d,ans,a[N];

main () {
	cin>>n>>l;
	
	if (n==1) {
		cout<<1<<endl;
		return 0;
	}
	
	for (int i=1; i<=n; i++) 
		cin>>a[i];

	sort(a+1,a+n+1);
	
	a[n+1]=100000;
	dp_[0][0][0]=1;
	for (int i=2; i<=n+1; i++) {
		for (int cc=1; cc<=n; cc++) {
			for (int p=0; p<=l; p++) {
				d=(a[i]-a[i-1])*(2*cc);
				if (d<=p) {
					dp[cc][p][0]=(dp[cc][p][0]+dp_[cc-1][p-d][0]*cc)%mod;
					dp[cc][p][0]=(dp[cc][p][0]+dp_[cc][p-d][0]*2*cc)%mod;
					dp[cc][p][0]=(dp[cc][p][0]+dp_[cc+1][p-d][0]*cc)%mod;
				}
				
				d=(a[i]-a[i-1])*(2*cc-1);
				if (d<=p) {
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc][p-d][0]*2)%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc-1][p-d][0]*2)%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc-1][p-d][1]*(cc-1))%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc][p-d][1]*(2*cc-1))%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc+1][p-d][1]*cc)%mod;
				}
			
				d=(a[i]-a[i-1])*(2*cc-2);	
				if (d<=p) {
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc][p-d][1])%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc-1][p-d][1])%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc-1][p-d][2]*(cc-2))%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc][p-d][2]*(2*cc-2))%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc+1][p-d][2]*cc)%mod;
				}
						
				if (i==n+1 && cc==1) 
					ans=(ans+dp[cc][p][2])%mod;
			}
		}
		
		for (int cc=0; cc<=n; cc++) 
			for (int p=0; p<=l; p++) 
				for (int t=0; t<3; ++t)
					dp_[cc][p][t]=dp[cc][p][t],dp[cc][p][t]=0;
	}

	cout<<ans<<"\n";
}

Compilation message (stderr)

skyscraper.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main () {
      |       ^

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