Submission #559531

#	Time	Username	Problem	Language	Result	Execution time	Memory
559531		Pherokung	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	139 ms	81892 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define L 1005
#define ll long long
const ll mod = 1e9+7;
int n,l,a[N];
ll dp[N][N][L][3],ans=0;
int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	
	if(n == 1){ // special case
		printf("1");
		return 0;
	}
	
	
	dp[1][1][0][0] = 1;
	dp[1][1][0][1] = 2;
	for(int idx=1;idx<n;idx++){
		for(int comp=1;comp<=idx;comp++){ 
			for(int sum=0;sum<=l;sum++){ 
				for(int ex=0;ex<=2;ex++){ // ex is number of endpoint(begin/end) which was filled
					int n_sum = sum + (2 * comp - ex) * (a[idx+1] - a[idx]); // add a[idx+1] to every available spaces
					ll val = dp[idx][comp][sum][ex];
					if(n_sum > l) continue;
					
					if(ex < 2){
						// add idx+1 to endpoint and merge to some components
						dp[idx+1][comp][n_sum][ex+1] += (2 - ex) * val;
						dp[idx+1][comp][n_sum][ex+1] %= mod;
						
						// add idx+1 to endpoint and create new component
						dp[idx+1][comp+1][n_sum][ex+1] += (2 - ex) * val;
						dp[idx+1][comp+1][n_sum][ex+1] %= mod;
					}
					
					// create new component
					dp[idx+1][comp+1][n_sum][ex] += (comp + 1 - ex) * val;
					dp[idx+1][comp+1][n_sum][ex] %= mod;
					
					// add to begin or end of component
					dp[idx+1][comp][n_sum][ex] += (2 * comp - ex) * val;
					dp[idx+1][comp][n_sum][ex] %= mod;
					
					// add and merge between two components
					dp[idx+1][comp-1][n_sum][ex] += (comp - 1) * val;
					dp[idx+1][comp-1][n_sum][ex] %= mod;
				}
			}
		}
	}
	
	for(int i=0;i<=l;i++) ans = (ans + dp[n][1][i][2]) % mod;
	printf("%lld",ans);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:11:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~

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