Submission #1303148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303148		fuyu	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	23 ms	24224 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ins insert
#define fi first
#define se second
#define ld long double
#define ALL(x) (x).begin(), (x).end()
#define MASK(x) (1ULL << (x))
#define BIT(x, k) ((x) >> (k) & 1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

template<typename T1, typename T2> bool maximize(T1 &x, const T2 &y){
	if (x < y){
		x = y;
		return 1;
	}
	return 0;
}

template<typename T1, typename T2> bool minimize(T1 &x, const T2 &y){
	if (x > y){
		x = y;
		return 1;
	}
	return 0;
}

bool ST_ALLOC;

#define file "SKYSCRAPER"

void fastio(){
	if (fopen(file".INP", "r")){
		freopen(file".INP", "r", stdin);
		freopen(file".OUT", "w", stdout);
	}
}

const int maxn = 1e2 + 9;
const int maxl = 1e3 + 5;
const int mod = 1e9 + 7;

void add(int &a, const int &b){
	a += b;
	if (a >= mod)
		a -= mod;
}

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

int n, l;
int a[maxn];
int dp[2][maxl][maxl][3];

/*
	Xét tới vị trí i và đang có x tplt,
	ta có thể:
		chèn i và để nối 2 tplt
		tạo một tplt mới là i
		bỏ i và đầu một tplt
		bỏ vi vào cuối một tplt
/*

/*
dp(i, j, k, s)
	i : số cách nhét i phần tử đầu vào hoán vị n
	j thành phần liên thông
	chi phí là k
	s : 0 -> chưa có 2 đầu mút
		1 -> có 1 đầu mút
		2 -> có 2 đầu mút
*/



bool EN_ALLOC;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	fastio();

	cin >> n >> l;

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

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

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

	for(int i = 1; i <= n; ++i){
		bool cur = i & 1, pre = cur ^ 1;

		memset(dp[cur], 0, sizeof(dp[cur]));

		for(int j = 1; j <= i; ++j)
			for(int k = 0; k <= l; ++k)
				for(int m = 0; m <= 2; ++m){
					int diff = a[i] - a[i - 1];
					int &ans = dp[cur][j][k][m];
					ans = 0;

					//Them 1 tplt moi, khong tao them dau mut
					int lastK = k - diff * (2 * (j - 1) - m);
					if (lastK >= 0 && j - m >= 1)
						add(ans,
							mul(dp[pre][j - 1][lastK][m], j - m));

					//Them 1 tplt moi, tao them 1 dau mut
					lastK = k - diff * (2 * (j - 1) - (m - 1));
					if (lastK >= 0 && m >= 1)
						add(ans,
							mul(dp[pre][j - 1][lastK][m - 1], 3 - m)); //3 - m la so dau mut con lai

					//Noi 2 tplt
					lastK = k - diff * (2 * (j + 1) - m);
					if (lastK >= 0 && j < i)
						add(ans,
							mul(dp[pre][j + 1][lastK][m], j));

					//Them vao 1 tplt bat ky, khong tao them dau mut
					lastK = k - diff * (2 * j - m);
					if (lastK >= 0)
						add(ans,
							mul(dp[pre][j][lastK][m], 2 * j - m));

					//Them vao 1 tplt bat ky, tao them dau mut
					lastK = k - diff * (2 * j - (m - 1));
					if (lastK >= 0 && m >= 1)
						add(ans,
							mul(dp[pre][j][lastK][m - 1], 3 - m));
				}
	}

	int res = 0;

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

	cout << res << '\n';


	cerr << "Time ran : " << TIME << "s\n";
	cerr << "Static memory used : " << fixed << setprecision(2) << (((&EN_ALLOC) - (&ST_ALLOC)) / (1.0l * 1024 * 1024)) << "mb\n";
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void fastio()':
skyscraper.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 freopen(file".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:39:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |                 freopen(file".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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