Submission #288260

#	Time	Username	Problem	Language	Result	Execution time	Memory
288260		sjimed	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	157 ms	114552 KiB

skyscraper

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

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
const ll Mod = 1e9 + 7;

int n, l;
int a[111];
ll dp[3][111][111][1010];

int main() {
	fast;

	cin >> n >> l;

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

	sort(a+1, a+n+1);

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

	for(int i=1; i<n; i++) {
		for(int j=1; j<=i; j++) {
			for(int k=0; k<=l; k++) {
				for(int t=0; t<=2; t++) {
					int p = k + (a[i+1] - a[i]) * (2 * j - t);
					if(p > l) continue;

					dp[t][i+1][j+1][p] += dp[t][i][j][k] * (j - t + 1);
					dp[t][i+1][j+1][p] %= Mod;

					dp[t][i+1][j][p] += dp[t][i][j][k] * (2 * j - t);
					dp[t][i+1][j][p] %= Mod;

					dp[t][i+1][j-1][p] += dp[t][i][j][k] * (j-1);
					dp[t][i+1][j-1][p] %= Mod;

					if(t < 2) {
						dp[t+1][i+1][j][p] += dp[t][i][j][k] * (2 - t);
						dp[t+1][i+1][j][p] %= Mod;

						dp[t+1][i+1][j+1][p] += dp[t][i][j][k] * (2 - t);
						dp[t+1][i+1][j+1][p] %= Mod;
					}
				}
			}
		}
	}

	ll ans = 0;
	for(int i=0; i<=l; i++) ans += dp[2][n][1][i];

	cout << ans % Mod;
}

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