Submission #962873

#	Time	Username	Problem	Language	Result	Execution time	Memory
962873		happy_node	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	567 ms	167880 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;

int N,L;
int A[105];
int dp[105][105][2005][3];

// optimistic cost -> lower bound of the cost
// we keep increasing this optimistic cost as we go on
// we increase this as many times as the number of open borders of connected components
// # of components equal to leftmost or rightmost fixed

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>L;
	for(int i=0;i<N;i++) cin>>A[i];

	if(N==1) {
		cout<<1<<'\n';
		return 0;
	}

	sort(A,A+N);

	// first lock or last lock
	dp[1][1][0][1]=2;

	// just middle 
	dp[1][1][0][0]=1;

	for(int i=1;i<N;i++) {
		int d=A[i]-A[i-1];
		for(int c=0;c<=N;c++) {
			for(int s=0;s<=L;s++) {
				for(int z=0;z<3;z++) {
					// merge 2 components
					if(c>0) {
						dp[i+1][c-1][s+d*(2*c-z)][z]+=1LL*dp[i][c][s][z]*(c-1)%mod;
						dp[i+1][c-1][s+d*(2*c-z)][z]%=mod;
					}

					// append to the beginning or end of one comp but don't lock
					dp[i+1][c][s+d*(2*c-z)][z]+=1ll*dp[i][c][s][z]*(2*c-z)%mod;
					dp[i+1][c][s+d*(2*c-z)][z]%=mod;

					// append to the beginning or end and lock
					dp[i+1][c][s+d*(2*c-z)][z+1]+=1ll*(2-z)*dp[i][c][s][z]%mod;
					dp[i+1][c][s+d*(2*c-z)][z+1]%=mod;

					// make new component

					// first or last component but not lock
					dp[i+1][c+1][s+d*(2*c-z)][z]+=1ll*(2-z)*dp[i][c][s][z]%mod;
					dp[i+1][c+1][s+d*(2*c-z)][z]%=mod;

					// first or last component and lock
					dp[i+1][c+1][s+d*(2*c-z)][z+1]+=1ll*(2-z)*dp[i][c][s][z]%mod;
					dp[i+1][c+1][s+d*(2*c-z)][z+1]%=mod;

					// make as middle component
					if(c>1) {
						dp[i+1][c+1][s+d*(2*c-z)][z]+=1ll*dp[i][c][s][z]*(c-1)%mod;
						dp[i+1][c+1][s+d*(2*c-z)][z]%=mod;
					}
				}
			}
		}
	}
		
	int ans=0;
	for(int s=0;s<=L;s++) {
		ans+=dp[N][1][s][2];
		ans%=mod;
	}
	cout<<ans<<'\n';

}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:34: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   50 |      dp[i+1][c][s+d*(2*c-z)][z+1]+=1ll*(2-z)*dp[i][c][s][z]%mod;
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:38:18: note: within this loop
   38 |     for(int z=0;z<3;z++) {
      |                 ~^~

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