oj.uz

Submission #961946

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

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

int N,L;
int A[105];
int dp[105][105][11133][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 348 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 5 ms 4184 KB Output is correct
4 Correct 30 ms 9300 KB Output is correct
5 Correct 42 ms 14684 KB Output is correct
6 Correct 42 ms 14536 KB Output is correct
7 Correct 43 ms 14608 KB Output is correct
8 Correct 43 ms 14672 KB Output is correct
9 Correct 54 ms 14620 KB Output is correct
10 Correct 42 ms 14676 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 29576 KB Output is correct
2 Correct 146 ms 38740 KB Output is correct
3 Correct 136 ms 38792 KB Output is correct
4 Correct 136 ms 38764 KB Output is correct
5 Correct 136 ms 38824 KB Output is correct
6 Correct 133 ms 38616 KB Output is correct
7 Correct 133 ms 38648 KB Output is correct
8 Correct 135 ms 38740 KB Output is correct
9 Correct 133 ms 38632 KB Output is correct
10 Correct 144 ms 38772 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 5 ms 4184 KB Output is correct
4 Correct 30 ms 9300 KB Output is correct
5 Correct 42 ms 14684 KB Output is correct
6 Correct 42 ms 14536 KB Output is correct
7 Correct 43 ms 14608 KB Output is correct
8 Correct 43 ms 14672 KB Output is correct
9 Correct 54 ms 14620 KB Output is correct
10 Correct 42 ms 14676 KB Output is correct
11 Correct 100 ms 29576 KB Output is correct
12 Correct 146 ms 38740 KB Output is correct
13 Correct 136 ms 38792 KB Output is correct
14 Correct 136 ms 38764 KB Output is correct
15 Correct 136 ms 38824 KB Output is correct
16 Correct 133 ms 38616 KB Output is correct
17 Correct 133 ms 38648 KB Output is correct
18 Correct 135 ms 38740 KB Output is correct
19 Correct 133 ms 38632 KB Output is correct
20 Correct 144 ms 38772 KB Output is correct
21 Correct 1191 ms 288208 KB Output is correct
22 Execution timed out 2085 ms 498964 KB Time limit exceeded
23 Halted 0 ms 0 KB -