Submission #961943

#	Time	Username	Problem	Language	Result	Execution time	Memory
961943		happy_node	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	468 ms	119164 KiB

skyscraper

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

const int mod=1e9+7, ofs=1000,MX=5005;

int N,L;
int A[105];
int dp[20][20][2*MX][2][2]; // harus nge offset 
// harus di flying table juga ni ntar kalo dah beres aja

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);

	dp[0][0][ofs][0][0]=1;

	// first lock
	dp[1][1][-A[0]+ofs][1][0]=1;

	// last lock
	dp[1][1][-A[0]+ofs][0][1]=1;

	// just middle biasa
	dp[1][1][-2*A[0]+ofs][0][0]=1;

	for(int i=1;i<N;i++) {
		for(int c=0;c<=N;c++) {
			for(int s=-MX+ofs;s<=MX+ofs;s++) {
				// merge two components
				if(c>0) {
					for(int l=0;l<2;l++) {
						for(int r=0;r<2;r++) {
							dp[i+1][c-1][s+2*A[i]][l][r]+=1ll*dp[i][c][s][l][r]*(c-1)%mod;	
							dp[i+1][c-1][s+2*A[i]][l][r]%=mod;	
						}
					}
				}

				// append to the beginning of one comp
				for(int l=0;l<2;l++) {
					for(int r=0;r<2;r++) {
						if(!l) { // belum locked yg pertama
							// tarok di pertama dan lock
							dp[i+1][c][s+A[i]][1][r]+=dp[i][c][s][l][r];
							dp[i+1][c][s+A[i]][1][r]%=mod;

							// tidak lock -> bukan yg pertama
							dp[i+1][c][s+A[i]-A[i]][l][r]+=1ll*dp[i][c][s][l][r]*c%mod;
							dp[i+1][c][s+A[i]-A[i]][l][r]%=mod;

							
						} else { // yg pertama sudah locked
							if(c>0) {
								dp[i+1][c][s+A[i]-A[i]][l][r]+=1ll*dp[i][c][s][l][r]*(c-1)%mod;
								dp[i+1][c][s+A[i]-A[i]][l][r]%=mod;
							}
						}
					}
				}


				// append to end of one comp
				for(int l=0;l<2;l++) {
					for(int r=0;r<2;r++) {
						if(!r) { // belum locked yg terakhir
							// tarok di terakhir dan lock
							dp[i+1][c][s+A[i]][l][1]+=dp[i][c][s][l][r];
							dp[i+1][c][s+A[i]][l][1]%=mod;

							// tidak lock -> bukan yg terakhir
							dp[i+1][c][s+A[i]-A[i]][l][r]+=1ll*dp[i][c][s][l][r]*c%mod;
							dp[i+1][c][s+A[i]-A[i]][l][r]%=mod;
						} else { // yg terakhir sudah locked
							if(c>0) {
								dp[i+1][c][s+A[i]-A[i]][l][r]+=1ll*dp[i][c][s][l][r]*(c-1)%mod;
								dp[i+1][c][s+A[i]-A[i]][l][r]%=mod;
							}
						}
					}
				}

				// make new comp

				// make as first component
				for(int r=0;r<2;r++) {
					int l=0;// first gaboleh locked

					// lock as first
					dp[i+1][c+1][s-A[i]][1][r]+=dp[i][c][s][l][r];
					dp[i+1][c+1][s-A[i]][1][r]%=mod;

					// not lock as first
					dp[i+1][c+1][s-2*A[i]][l][r]+=dp[i][c][s][l][r];
					dp[i+1][c+1][s-2*A[i]][l][r]%=mod;
				}

				// make as last component
				for(int l=0;l<2;l++) {
					int r=0; // last gboleh locked

					// lock as last
					dp[i+1][c+1][s-A[i]][l][1]+=dp[i][c][s][l][r];
					dp[i+1][c+1][s-A[i]][l][1]%=mod;

					if(c>0) {
						// not lock as last
						dp[i+1][c+1][s-2*A[i]][l][r]+=dp[i][c][s][l][r];
						dp[i+1][c+1][s-2*A[i]][l][r]%=mod;
					}
				}

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

}

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