Submission #445511

#	Time	Username	Problem	Language	Result	Execution time	Memory
445511		KYoA_A	Skyscraper (JOI16_skyscraper)	C++17	5 / 100	4 ms	1612 KiB

skyscraper

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define kyoa_a
#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define vt vector
#define ar array
#define pii pair<int, int>
#define vi vector<int>
#define pll pair<ll, ll>
#define pct(x) __builtin_popcount(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define rsz resize
#define bk back()

constexpr int log2(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const int mod = 1e9 + 7;
const int N = 101;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

int dp[N][N][1005][3], a[N];
int n, L;

void solve(){
	cin >> n >> L;


	rep(i, 1, n+1) cin >> a[i];
	if(n == 1){cout << 1 << '\n'; return;}
	sort(a+1, a+n+1);

	dp[0][0][0][0] = 1;
	rep(i, 1, n+1) rep(j, 1, i+1) rep(l, 0, 1001){
		int nl = l - (a[i] - a[i-1])*2*(j - 1);
		if(nl >= 0){
			dp[i][j][l][0] += dp[i-1][j-1][nl][0]*j;
			dp[i][j][l][1] += dp[i-1][j-1][nl][0]*2;
			nl -= 2*(a[i] - a[i-1]);
			if(nl >= 0){
				dp[i][j][l][0] += dp[i-1][j][nl][0]*2*j;
				dp[i][j][l][1] += dp[i-1][j][nl][0]*2;
				nl -= 2*(a[i] - a[i-1]);
				if(nl >= 0){
					dp[i][j][l][0] += dp[i-1][j+1][nl][0]*(j);
				}
				nl += 2*(a[i] - a[i-1]);
			}
			nl += 2*(a[i] - a[i-1]);
		}
		nl += (a[i] - a[i-1]);
		if(nl >= 0){
			dp[i][j][l][1] += dp[i-1][j-1][nl][1]*(j-1);
			dp[i][j][l][2] += dp[i-1][j-1][nl][1];
			nl -= 2*(a[i] - a[i-1]);
			if(nl >= 0){
				dp[i][j][l][1] += dp[i-1][j][nl][1]*(2*j - 1);
				dp[i][j][l][2] += dp[i-1][j][nl][1];
				nl -= 2*(a[i] - a[i-1]);
				if(nl >= 0){
					dp[i][j][l][1] += dp[i-1][j+1][nl][1]*(j);

				}
				nl += 2*(a[i] - a[i-1]);
			}
			nl += 2*(a[i] - a[i-1]);
		}
		nl += a[i] - a[i-1];
		if(nl >= 0){
			dp[i][j][l][2] += dp[i-1][j-1][nl][2]*max(0, j-2);
			nl -= 2*(a[i] - a[i-1]);
			if(nl >= 0){
				dp[i][j][l][2] += dp[i-1][j][nl][2]*(2*(j-1));
				nl -= 2*(a[i] - a[i-1]);
				if(nl >= 0){
					dp[i][j][l][2] += dp[i-1][j+1][nl][2]*j;
				}
			}
		}
	}

	int ans = 0;
	rep(l, 0, L+1) ans += dp[n][1][l][2];
	cout << ans << '\n';
}


int main(){
	#ifdef kyoa_a
		auto begin = std::chrono::high_resolution_clock::now();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
		solve();

	#ifdef kyoa_a
		auto end = std::chrono::high_resolution_clock::now();
		cout << setprecision(3) << fixed;
		cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
	#endif
}

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