oj.uz

Submission #961944

# Submission time Handle Problem Language Result Execution time Memory
961944 2024-04-12T19:36:39 Z happy_node Skyscraper (JOI16_skyscraper) C++17
20 / 100
 467 ms 119124 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7, ofs=5005,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 2908 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 21 ms 8784 KB Output is correct
5 Correct 38 ms 13316 KB Output is correct
6 Correct 40 ms 13392 KB Output is correct
7 Correct 43 ms 13492 KB Output is correct
8 Correct 38 ms 13404 KB Output is correct
9 Correct 38 ms 13412 KB Output is correct
10 Correct 39 ms 13392 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 26708 KB Output is correct
2 Correct 120 ms 35152 KB Output is correct
3 Correct 120 ms 35068 KB Output is correct
4 Correct 124 ms 35184 KB Output is correct
5 Correct 135 ms 35112 KB Output is correct
6 Correct 120 ms 35188 KB Output is correct
7 Correct 122 ms 35252 KB Output is correct
8 Correct 120 ms 35156 KB Output is correct
9 Correct 124 ms 35152 KB Output is correct
10 Correct 121 ms 34956 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 2908 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 21 ms 8784 KB Output is correct
5 Correct 38 ms 13316 KB Output is correct
6 Correct 40 ms 13392 KB Output is correct
7 Correct 43 ms 13492 KB Output is correct
8 Correct 38 ms 13404 KB Output is correct
9 Correct 38 ms 13412 KB Output is correct
10 Correct 39 ms 13392 KB Output is correct
11 Correct 90 ms 26708 KB Output is correct
12 Correct 120 ms 35152 KB Output is correct
13 Correct 120 ms 35068 KB Output is correct
14 Correct 124 ms 35184 KB Output is correct
15 Correct 135 ms 35112 KB Output is correct
16 Correct 120 ms 35188 KB Output is correct
17 Correct 122 ms 35252 KB Output is correct
18 Correct 120 ms 35156 KB Output is correct
19 Correct 124 ms 35152 KB Output is correct
20 Correct 121 ms 34956 KB Output is correct
21 Runtime error 467 ms 119124 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -