oj.uz

Submission #962871

# Submission time Handle Problem Language Result Execution time Memory
962871 2024-04-14T09:13:23 Z happy_node Skyscraper (JOI16_skyscraper) C++17
15 / 100
 4 ms 3676 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;

int N,L;
int A[105];
int dp[105][105][1005][3];

// optimistic cost -> lower bound of the cost
// we keep increasing this optimistic cost as we go on
// we increase this as many times as the number of open borders of connected components
// # of components equal to leftmost or rightmost fixed

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

	// first lock or last lock
	dp[1][1][0][1]=2;

	// just middle 
	dp[1][1][0][0]=1;

	for(int i=1;i<N;i++) {
		int d=A[i]-A[i-1];
		for(int c=0;c<=N;c++) {
			for(int s=0;s<=L;s++) {
				for(int z=0;z<3;z++) {
					// merge 2 components
					if(c>0) {
						dp[i+1][c-1][s+d*(2*c-z)][z]+=1LL*dp[i][c][s][z]*(c-1)%mod;
						dp[i+1][c-1][s+d*(2*c-z)][z]%=mod;
					}

					// append to the beginning or end of one comp but don't lock
					dp[i+1][c][s+d*(2*c-z)][z]+=1ll*dp[i][c][s][z]*(2*c-z)%mod;
					dp[i+1][c][s+d*(2*c-z)][z]%=mod;

					// append to the beginning or end and lock
					dp[i+1][c][s+d*(2*c-z)][z+1]+=1ll*(2-z)*dp[i][c][s][z]%mod;
					dp[i+1][c][s+d*(2*c-z)][z+1]%=mod;

					// make new component

					// first or last component but not lock
					dp[i+1][c+1][s+d*(2*c-z)][z]+=1ll*(2-z)*dp[i][c][s][z]%mod;
					dp[i+1][c+1][s+d*(2*c-z)][z]%=mod;

					// first or last component and lock
					dp[i+1][c+1][s+d*(2*c-z)][z+1]+=1ll*(2-z)*dp[i][c][s][z]%mod;
					dp[i+1][c+1][s+d*(2*c-z)][z+1]%=mod;

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

}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:34: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   50 |      dp[i+1][c][s+d*(2*c-z)][z+1]+=1ll*(2-z)*dp[i][c][s][z]%mod;
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:38:18: note: within this loop
   38 |     for(int z=0;z<3;z++) {
      |                 ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Incorrect 4 ms 3420 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 2 ms 3416 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3416 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Incorrect 4 ms 3420 KB Output isn't correct
6 Halted 0 ms 0 KB -