Submission #329735

#	Time	Username	Problem	Language	Result	Execution time	Memory
329735		GioChkhaidze	Skyscraper (JOI16_skyscraper)	C++14	15 / 100	1 ms	636 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;
	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)
						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: 0 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80