oj.uz

Submission #961943

# Submission time Handle Problem Language Result Execution time Memory
961943 2024-04-12T19:36:10 Z happy_node Skyscraper (JOI16_skyscraper) C++17
20 / 100
 468 ms 119164 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 5 ms 3928 KB Output is correct
4 Correct 21 ms 8784 KB Output is correct
5 Correct 39 ms 13404 KB Output is correct
6 Correct 38 ms 13448 KB Output is correct
7 Correct 45 ms 13436 KB Output is correct
8 Correct 40 ms 13488 KB Output is correct
9 Correct 39 ms 13360 KB Output is correct
10 Correct 40 ms 13404 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 26704 KB Output is correct
2 Correct 124 ms 34976 KB Output is correct
3 Correct 121 ms 34940 KB Output is correct
4 Correct 120 ms 34956 KB Output is correct
5 Correct 126 ms 35100 KB Output is correct
6 Correct 131 ms 35008 KB Output is correct
7 Correct 122 ms 34968 KB Output is correct
8 Correct 123 ms 35032 KB Output is correct
9 Correct 121 ms 35152 KB Output is correct
10 Correct 139 ms 34980 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 5 ms 3928 KB Output is correct
4 Correct 21 ms 8784 KB Output is correct
5 Correct 39 ms 13404 KB Output is correct
6 Correct 38 ms 13448 KB Output is correct
7 Correct 45 ms 13436 KB Output is correct
8 Correct 40 ms 13488 KB Output is correct
9 Correct 39 ms 13360 KB Output is correct
10 Correct 40 ms 13404 KB Output is correct
11 Correct 88 ms 26704 KB Output is correct
12 Correct 124 ms 34976 KB Output is correct
13 Correct 121 ms 34940 KB Output is correct
14 Correct 120 ms 34956 KB Output is correct
15 Correct 126 ms 35100 KB Output is correct
16 Correct 131 ms 35008 KB Output is correct
17 Correct 122 ms 34968 KB Output is correct
18 Correct 123 ms 35032 KB Output is correct
19 Correct 121 ms 35152 KB Output is correct
20 Correct 139 ms 34980 KB Output is correct
21 Runtime error 468 ms 119164 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -