oj.uz

Submission #961942

# Submission time Handle Problem Language Result Execution time Memory
961942 2024-04-12T19:33:16 Z happy_node Skyscraper (JOI16_skyscraper) C++17
15 / 100
 30 ms 9052 KB 
#include <bits/stdc++.h>
using namespace std;

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

int N,L;
int A[105];
int dp[105][105][2005][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=-1000+ofs;s<=1000+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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 5 ms 3676 KB Output is correct
5 Correct 10 ms 4480 KB Output is correct
6 Correct 8 ms 4700 KB Output is correct
7 Correct 11 ms 4700 KB Output is correct
8 Correct 9 ms 4700 KB Output is correct
9 Incorrect 11 ms 4700 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7260 KB Output is correct
2 Correct 24 ms 9052 KB Output is correct
3 Correct 25 ms 9044 KB Output is correct
4 Correct 26 ms 9048 KB Output is correct
5 Correct 27 ms 9040 KB Output is correct
6 Correct 29 ms 8904 KB Output is correct
7 Correct 30 ms 9044 KB Output is correct
8 Correct 25 ms 9048 KB Output is correct
9 Correct 26 ms 8916 KB Output is correct
10 Correct 25 ms 9052 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 1 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 5 ms 3676 KB Output is correct
5 Correct 10 ms 4480 KB Output is correct
6 Correct 8 ms 4700 KB Output is correct
7 Correct 11 ms 4700 KB Output is correct
8 Correct 9 ms 4700 KB Output is correct
9 Incorrect 11 ms 4700 KB Output isn't correct
10 Halted 0 ms 0 KB -