Submission #646835

#	Time	Username	Problem	Language	Result	Execution time	Memory
646835		GusterGoose27	Skyscraper (JOI16_skyscraper)	C++11	15 / 100	1 ms	724 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 101;
const ll MAXL = 2001;
const ll MOD = 1e9+7;
ll n, l;
ll heights[MAXN];
ll dp[MAXN][MAXN][MAXL][2][2]; // number of elems, number of cc, value if all other things are next value, left occupied, right occupied

/*
Transitions:

We can create a new cc, add to an existing one, or merge two

New cc:
	Rescale all cc boundaries to the next increment
	open spaces = cc-1
	current value = 2*next-cur elem
	this could go in any of the open spaces

*/

void dpa(ll &a, ll &b) {
	a += b;
	a %= MOD;
}

// void dpa(ll &a, ll &b) {
// 	a += b;
// 	a %= MOD;
// }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> l;
	for (ll i = 0; i < n; i++) cin >> heights[i];
	sort(heights, heights+n);
	ll curv = 2*(heights[1]-heights[0]);;
	if (curv <= l) dp[1][1][curv][0][0] = 1;
	curv += heights[0]-heights[1];
	if (curv <= l) {
		dp[1][1][curv][1][0] = 1;
		dp[1][1][curv][0][1] = 1;
	}
	heights[n] = heights[n-1];
	for (ll i = 2; i <= n; i++) {
		for (ll j = 1; j <= min(i, n+1-i); j++) {
			for (ll v = 0; v <= l; v++) {
				for (ll lo = 0; lo < 2; lo++) {
					for (ll ro = 0; ro < 2; ro++) {
						if (j > 1) {
							ll bounds = 2*(j-1)-lo-ro;
							ll ex = (heights[i]-heights[i-1])*bounds+2*heights[i]-2*heights[i-1];
							if (ex <= v) {
								ll cur = (ll) (j-lo-ro)*dp[i-1][j-1][v-ex][lo][ro];
								cur %= MOD;
								dpa(dp[i][j][v][lo][ro], cur);
							}
							ll nex = ex;
							if (nex <= v) {
								if (lo) dpa(dp[i][j][v][lo][ro], dp[i-1][j-1][v-nex][0][ro]);
								if (ro) dpa(dp[i][j][v][lo][ro], dp[i-1][j-1][v-nex][lo][0]);
							}
						}
						ll bounds = 2*j-lo-ro;
						ll ex = (heights[i]-heights[i-1])*bounds;
						if (ex <= v) {
							ll cur = (ll) (2*j-lo-ro)*dp[i-1][j][v-ex][lo][ro];
							cur %= MOD;
							dpa(dp[i][j][v][lo][ro], cur);
						}
						ll nex = ex;
						if (nex <= v) {
							if (lo) dpa(dp[i][j][v][lo][ro], dp[i-1][j][v-nex][0][ro]);
							if (ro) dpa(dp[i][j][v][lo][ro], dp[i-1][j][v-nex][lo][0]);
						}
						bounds = 2*j-lo-ro;
						ex = (heights[i]-heights[i-1])*bounds;
						if (ex <= v) {
							ll cur = (ll) (j)*dp[i-1][j+1][v-ex][lo][ro];
							cur %= MOD;
							dpa(dp[i][j][v][lo][ro], cur);
						}
					}
				}
			}
		}
	}
	ll ans = 0;
	for (ll i = 0; i <= l; i++) {
		dpa(ans, dp[n][1][i][1][1]);
	}
	cout << ans << "\n";
}

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