Submission #740065

#	Time	Username	Problem	Language	Result	Execution time	Memory
740065		sentheta	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	75 ms	81856 KiB

skyscraper

// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
const Int MOD = 1e9+7;
// const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}







const int N = 105;
const int M = 1005;

int n, m;
int a[N];

int dp[N][N][M][3];


void solve(){
	
	cin >> n >> m;
	if(n==1){
		cout << 1 << nl; return;
	}

	rep(i,1,n+1){
		cin >> a[i];
	}
	sort(a+1,a+1+n);

	// ONE is first/last
	dp[1][1][0][1] = 2;
	// ONE is middle
	dp[1][1][0][0] = 1;

	for(int x=2; x<=n; x++)
	for(int j=1; j<=x-1; j++)
	for(int k=0; k<=m; k++){
		int jmp = a[x]-a[x-1], val, nxtk;
		
		nxtk = k+(2*j-0)*jmp;
		val = dp[x-1][j][k][0]%MOD;
		if(nxtk <= m){
			// append at a component
			dp[x][j][nxtk][0] += (2*j-0)*val;
			// append at a component and end it
			dp[x][j][nxtk][1] += 2*val;
			// merge two components
			dp[x][j-1][nxtk][0] += (j-1)*val;
			// new component at middle
			dp[x][j+1][nxtk][0] += (j+1)*val;
			// new component at end
			dp[x][j+1][nxtk][1] += 2*val;
		}


		nxtk = k+(2*j-1)*jmp;
		val = dp[x-1][j][k][1]%MOD;
		if(nxtk <= m){
			// append at a component
			dp[x][j][nxtk][1] += (2*j-1)*val;
			// append at a component and end it
			dp[x][j][nxtk][2] += val;
			// merge two components
			dp[x][j-1][nxtk][1] += (j-1)*val;
			// new component at middle
			dp[x][j+1][nxtk][1] += j*val;
			// new component at end
			dp[x][j+1][nxtk][2] += val;
		}

		nxtk = k+(2*j-2)*jmp;
		val = dp[x-1][j][k][2]%MOD;
		if(nxtk <= m){
			// append at a component
			dp[x][j][nxtk][2] += (2*j-2)*val;
			// append at a component and end it
			;
			// merge two components
			dp[x][j-1][nxtk][2] += (j-1)*val;
			// new component at middle
			dp[x][j+1][nxtk][2] += (j-1)*val;
			// new component at end
			;
		}
	}

	// dbg(dp[1][1][0][1]);
	// dbg(dp[2][2][1][2]);
	// dbg(dp[3][1][3][2]);

	int ans = 0;
	rep(k,0,m+1){
		// if(dp[n][1][k][2]){
		// 	dbg(k);
		// 	dbg(dp[n][1][k][2]);
		// }
		(ans += dp[n][1][k][2] )%=MOD;
	}
	ans = (ans%MOD+MOD)%MOD;
	cout << ans << nl;
	
	
	
}

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