oj.uz

Submission #646835

# Submission time Handle Problem Language Result Execution time Memory
646835 2022-09-30T20:45:10 Z GusterGoose27 Skyscraper (JOI16_skyscraper) C++11
15 / 100
 1 ms 724 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
0 / 80.0

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