oj.uz

Submission #329735

# Submission time Handle Problem Language Result Execution time Memory
329735 2020-11-22T09:35:36 Z GioChkhaidze Skyscraper (JOI16_skyscraper) C++14
15 / 100
 1 ms 636 KB 
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=103;
const int L=1004;

ll mod=1e9+7;
ll dp[N][L][3];
ll dp_[N][L][3];
ll n,l,d,ans,a[N];

main () {
	cin>>n>>l;
	for (int i=1; i<=n; i++) 
		cin>>a[i];

	sort(a+1,a+n+1);
	
	a[n+1]=100000;
	dp_[0][0][0]=1;
	for (int i=2; i<=n+1; i++) {
		for (int cc=1; cc<=n; cc++) {
			for (int p=0; p<=l; p++) {
				d=(a[i]-a[i-1])*(2*cc);
				if (d<=p) {
					dp[cc][p][0]=(dp[cc][p][0]+dp_[cc-1][p-d][0]*cc)%mod;
					dp[cc][p][0]=(dp[cc][p][0]+dp_[cc][p-d][0]*2*cc)%mod;
					dp[cc][p][0]=(dp[cc][p][0]+dp_[cc+1][p-d][0]*cc)%mod;
				}
				
				d=(a[i]-a[i-1])*(2*cc-1);
				if (d<=p) {
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc][p-d][0]*2)%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc-1][p-d][0]*2)%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc-1][p-d][1]*(cc-1))%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc][p-d][1]*(2*cc-1))%mod;
					dp[cc][p][1]=(dp[cc][p][1]+dp_[cc+1][p-d][1]*cc)%mod;
				}
			
				d=(a[i]-a[i-1])*(2*cc-2);	
				if (d<=p) {
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc][p-d][1])%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc-1][p-d][1])%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc-1][p-d][2]*(cc-2))%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc][p-d][2]*(2*cc-2))%mod;
					dp[cc][p][2]=(dp[cc][p][2]+dp_[cc+1][p-d][2]*cc)%mod;
					
					if (i==n+1)
						ans=(ans+dp[cc][p][2])%mod;
				}
			}
		}
		
		for (int cc=0; cc<=n; cc++) 
			for (int p=0; p<=l; p++) 
				for (int t=0; t<3; ++t)
					dp_[cc][p][t]=dp[cc][p][t],dp[cc][p][t]=0;
	}

	cout<<ans<<"\n";
}

Compilation message

skyscraper.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main () {
      |       ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 636 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -