Submission #112380

#	Time	Username	Problem	Language	Result	Execution time	Memory
112380		MAMBA	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	33 ms	5632 KiB

skyscraper

#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 100 + 10;
constexpr int L = 1010;

constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

int n , l;

ll dp[2][N][L][3], arr[N];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

#ifndef LOCAL
	//	fileIO("forbidden1");
#endif

	cin >> n >> l;

	if (n == 1) return cout << 1 << endl, 0;

	rep(i , 0 , n) cin >> arr[i];
	sort(arr, arr + n);
	rep(i , 0 , n)
		arr[i] = arr[i + 1] - arr[i];

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

	rep(i , 0 , n - 1) {
		int id = i & 1;
		rep(j , 1 , i + 2) {
			rep(z , 0 , l + 1) {
				// sar o tah 0 baste
				{
					ll me = dp[id][j][z][0];
					ll EN = 2 * j;
					// merge
					if (j > 1 && (EN - 2) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][0] , (j - 1) * me);
					// sar ya tah
					//     endpoint bashe
					if ((EN - 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][(EN - 1) * arr[i + 1] + z][1] , 2 * me);
					// 	   on vasata bashe
					if  (EN	* arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][EN	* arr[i + 1] + z][0] , me * EN); 
					// jadid
					if ((EN + 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][0] , me * (j + 1)); 
					if ((EN + 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j + 1][(EN + 1) * arr[i + 1] + z][1] , me * 2);

				}
				// sar o tah 1 baste
				{
					ll me = dp[id][j][z][1];
					ll EN = 2 * j - 1;
					// merge
					if (j > 1 && (EN - 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][1] , (j - 1) * me); 
					// sar ya tah
					//   	endpoint
					if ((EN - 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][(EN - 1) * arr[i + 1] + z][2] , me);
					//  	on vasata
					if  (EN	* arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][EN	* arr[i + 1] + z][1] , me * EN); 
					// jadid
					if ((EN + 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][1] , me * j); 
					if ((EN + 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j + 1][(EN + 1) * arr[i + 1] + z][2] , me);
				}
				// sar o tah 2 baste
				{
					ll me = dp[id][j][z][2];
					ll EN = 2 * j - 2;
					// merge
					if (j > 1 && (EN - 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][2] , (j - 1) * me); 
					// sar ya tah
					//  	on vasata
					if  (EN	* arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][EN	* arr[i + 1] + z][2] , me * EN); 
					// jadid
					if ((EN + 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][2] , me * (j - 1)); 	
				}
			}
		}
		memset(dp[id] , 0 , sizeof(dp[id]));
	}
/*
	rep(j , 1 , n + 1)
	   rep(z , 0 , l + 1) {
			cout << j << ' '<< z << ' '<< dp[(n - 1) & 1][j][z][2] << endl;
	   }	*/   
	ll res = 0;
	rep(i , 0 , l + 1) {
		add(res , dp[(n - 1) & 1][1][i][2]);
	}
	cout << res << endl;
	return 0;
}

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