Submission #559528

#	Time	Username	Problem	Language	Result	Execution time	Memory
559528		Pherokung	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	128 ms	37560 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define L 1005
const int mod = 1e9+7;
int n,l,a[N],dp[N][N][L][3],ans=0;
int add(int a,int b){
	return ((a % mod)+(b % mod)) % mod;
}
int mul(int a,int b){
	return ((long long)(a * b)) % mod;
}
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
					int 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] = add(dp[idx+1][comp][n_sum][ex+1], mul((2 - ex), val));
						// add idx+1 to endpoint and create new component
						dp[idx+1][comp+1][n_sum][ex+1] = add(dp[idx+1][comp+1][n_sum][ex+1], mul((2 - ex), val));
					}
					
					// create new component
					dp[idx+1][comp+1][n_sum][ex] = add(dp[idx+1][comp+1][n_sum][ex], mul((comp + 1 - ex), val));
					
					// add to begin or end of component
					dp[idx+1][comp][n_sum][ex] = add(dp[idx+1][comp][n_sum][ex], mul((2 * comp - ex), val));
					
					// add and merge between two components
					dp[idx+1][comp-1][n_sum][ex] = add(dp[idx+1][comp-1][n_sum][ex], mul((comp - 1), val));
				}
			}
		}
	}
	
	for(int i=0;i<=l;i++) ans = add(ans, dp[n][1][i][2]);
	printf("%d",ans);
}

Compilation message (stderr)

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

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