Submission #1147570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147570		raspy	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	84 ms	76992 KiB

skyscraper

#include <bits/stdc++.h>

#define int long long
#define vi vector<int>
#define ii pair<int, int>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define P 31
#define mod 1'000'000'007
#define inf 1'000'000'000'000
#define pb push_back
#define str string
#define sz(x) (x).size()
#define vvi vector<vi>
#define fun function
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define file freopen("problemname.in", "r", stdin); freopen("pr.out", "w", stdout);
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

using namespace std;
template <class T, int SZ> using arr = array<T, SZ>;

int a[101];
int dp[101][101][1001][3];

void solve()
{
	int n, l;
	cin >> n >> l;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a+1, a+n+1);
	a[n+1] = 10001;
	if (n==1)
	{
		cout << 1 << "\n";
		return;
	}
	dp[0][0][0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			for (int cl = 0; cl <= l; cl++)
				for (int m = 0; m <= 2; m++)
				{
					int dvig_cn = (2*j-m)*(a[i+1]-a[i]);
					if (dvig_cn > cl) continue;
					int pr_cn = cl-dvig_cn;
					dp[i][j][cl][m] += dp[i-1][j-1][pr_cn][m]; // dodaj zasebe
					dp[i][j][cl][m] += (2*j-m)*dp[i-1][j][pr_cn][m]; // dodaj k ze obstojecemu, samo ne
						// pred zacetek / konec
					if (m) // dodaj na zacetek/konec
						dp[i][j][cl][m] += (m==2?1:2)*dp[i-1][j-1][pr_cn][m-1];
					// dodamo k obstojecemu, tak da vsebuje zac/kon
					if (m==1)
						dp[i][j][cl][m] += 2*j*dp[i-1][j][pr_cn][m-1];
					if (m==2)
					{
						dp[i][j][cl][m] += (j-1)*dp[i-1][j][pr_cn][m-1];
						if (i==n)
							dp[i][j][cl][m] += dp[i-1][j][pr_cn][m-1];
					}
					// zdruzimo dve obstojeci
					if (m == 0)
						dp[i][j][cl][m] += (j)*(j+1)*dp[i-1][j+1][pr_cn][m];
					else if (m==1)
						dp[i][j][cl][m] += j*j*dp[i-1][j+1][pr_cn][m];
					else if (m==2)
					{
						if (i == n)
							dp[i][j][cl][m] += dp[i-1][j+1][pr_cn][m];
						dp[i][j][cl][m] += j*(j-1)*dp[i-1][j+1][pr_cn][m];
					}
					dp[i][j][cl][m] %= mod;
				}
	int rez = 0;
	for (int cl = 0; cl <= l; cl++)
		rez += dp[n][1][cl][2];
	cout << rez%mod << "\n";
}

signed main()
{
	oopt;
	int t = 1;
	// cin >> t;
	while (t--)
		solve();
	return 0;
}

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