Submission #559523

#	Time	Username	Problem	Language	Result	Execution time	Memory
559523		Pherokung	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	203 ms	69044 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define L 1005
#define ll long long
const ll mod = 1e9+7;
ll n,l,a[N],dp[N][N][L][3], ans = 0;
ll add(ll a,ll b){
	return ((a % mod)+(b % mod)) % mod;
}
int main(){
	scanf("%lld%lld",&n,&l);
	for(int i=1;i<=n;i++) scanf("%lld",&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])) % mod; // 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],(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],(2 - ex) * val);
					}
					
					// create new component
					dp[idx+1][comp+1][n_sum][ex] = add(dp[idx+1][comp+1][n_sum][ex], (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], (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], (comp - 1) * val);
				}
			}
		}
	}
	
	for(int i=0;i<=l;i++) ans = add(ans, dp[n][1][i][2]);
	printf("%lld",ans);
}

Compilation message (stderr)

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

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