Submission #1226885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226885		Tob	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	1 ms	1096 KiB

skyscraper

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 101, K = 1001, mod = 1e9 + 7;

inline int add(int x, int y) {return x+y<mod ? x+y : x+y-mod;}
inline int mul(int x, int y) {return (ll)x*y%mod;}

int n, l;
int a[N];
int dp[N][N][K][3];

int main () {
	FIO;
	cin >> n >> l;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	dp[0][1][0][0] = 1;
	dp[0][1][0][1+(n==1)] = 2-(n==1);
	for (int i = 1; i < n; i++) {
		int x = a[i]-a[i-1];
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k <= l; k++) {
				for (int g = 0; g < 3; g++) {
					if (k >= (2*j-2-g)*x && j > 1) {
						dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j-1][k-(2*j-2-g)*x][g], j-g));
						if (g) dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j-1][k-(2*j-2-g+1)*x][g-1], 3-g));
					}
					if (k >= (2*j-g)*x) {
						dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j][k-(2*j-g)*x][g], 2*j-g));
						if (g) dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j][k-(2*j-g+1)*x][g-1], 3-g));
					}
					if (k >= (2*j+2-g)*x && j <= n) {
						dp[i][j][k][g] = add(dp[i][j][k][g], mul(dp[i-1][j+1][k-(2*j+2-g)*x][g], j));
					}
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= l; i++) res = add(res, dp[n-1][1][i][2]);
	cout << res;

	return 0;
}

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