Submission #1155828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155828		mat_jur	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	635 ms	558476 KiB

skyscraper

#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int mod = 1'000'000'007;

int add(int a, int b) {
	a += b;
	return a >= mod ? a - mod : a;
}	

int mul(int a, int b) {
	return int(((ll)a*b)%mod);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, l;
	cin >> n >> l;
	vector<int> a(n);
	for (int &x : a) cin >> x;
	
	if (n == 1) {cout << "1 \n"; return 0;}

	sort(all(a));
	debug(a);

	vector dp(n+1, vector(l+1, vector(n+1, vector(3, 0))));

	dp[0][0][0][0] = 1;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= l; ++j) {
			for (int k = 0; k <= n; ++k) {
				for (int c = 0; c <= 2; ++c) {
					int s = j + (2 * k - c) * (i > 0 ? a[i] - a[i-1] : 0);
					assert(s >= 0 || dp[i][j][k][c] == 0);
					if (s > l || dp[i][j][k][c] == 0) continue;

					debug(vector<int>({i, j, k, c}));
					debug(s);
					debug(dp[i][j][k][c]);

					if (2*k-c) {
						dp[i+1][s][k][c] = add(dp[i+1][s][k][c], mul(2*k-c, dp[i][j][k][c]));
					}
					if (c+1 <= 2 && 2 * k - c) {
						dp[i+1][s][k][c+1] = add(dp[i+1][s][k][c+1], mul(2 - c, dp[i][j][k][c]));
					}
					if (k >= 2) {
						dp[i+1][s][k-1][c] = add(dp[i+1][s][k-1][c], mul(k-1, dp[i][j][k][c]));
					}
					if (k+1 <= n) {
						dp[i+1][s][k+1][c] = add(dp[i+1][s][k+1][c], mul(k+1 - c, dp[i][j][k][c]));
					}
					if (k+1 <= n && c+1 <= 2) {
						dp[i+1][s][k+1][c+1] = add(dp[i+1][s][k+1][c+1], mul(2 - c, dp[i][j][k][c]));
					}
				}
			}
		}
	}

	int res = 0;
	for (int i = 0; i <= l; ++i) res = add(res, dp[n][i][1][2]);

	cout << res << '\n';
	
	return 0;
}

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