Submission #1038315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038315		Hamed_Ghaffari	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	297 ms	101460 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MXN = 105;
const int MXL = 1005;
const int INF = 1e5 + 5;
const int MOD = 1e9 + 7;

int n, L, a[MXN];
ll dp[MXN][MXN][MXL][2][2];

int32_t main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n >> L;
	for(int i=1; i<=n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	a[n+1] = INF;
	dp[1][1][0][0][0] = 1;
	if(a[2]-a[1]<=L) dp[1][1][a[2]-a[1]][0][1] = dp[1][1][a[2]-a[1]][1][0] = 1;
	if((a[2]-a[1])*2<=L) dp[1][1][(a[2]-a[1])<<1][1][1] = 1;
	for(int i=1; i<n; i++)
		for(int j=1; j<=i; j++)
			for(int k=0; k<=L; k++)
				for(int b1 : {0, 1})
					for(int b2 : {0, 1}) {
						if(b1) {
							int kk = k + (2*(j-1)+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*(j-1)+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j][kk][0][b2] += dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*j+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j+1][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*j+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j+1][kk][0][b2] += dp[i][j][k][b1][b2]) %= MOD;
						}
						if(b2) {
							int kk = k + (2*(j-1)+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*(j-1)+b1)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j][kk][b1][0] += dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*j+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j+1][kk][b1][b2] += dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*j+b1)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j+1][kk][b1][0] += dp[i][j][k][b1][b2]) %= MOD;
						}
						if(j>1) {
							int kk = k + (2*(j-1)+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j][kk][b1][b2] += 2*(j-1)*dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*j+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j+1][kk][b1][b2] += (j-1)*dp[i][j][k][b1][b2]) %= MOD;
							kk = k + (2*(j-2)+b1+b2)*(a[i+2]-a[i+1]);
							if(kk<=L) (dp[i+1][j-1][kk][b1][b2] += (j-1)*dp[i][j][k][b1][b2]) %= MOD;
						}
					}
	ll ans = 0;
	for(int i=0; i<=L; i++)
		(ans += dp[n][1][i][0][0]) %= MOD;
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80