Submission #1036940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036940		arashMLG	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	73 ms	51536 KiB

skyscraper

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...)    69
#define debugArr(...)  69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 100 + 23;
const int M = 1000 + 23;
const ll inf = 1e18;
const ll mod = 1e9 + 7;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)
#define int         ll

void ok(int &x) {
	if(x < 0) x += mod*mod;
	x %= mod;
}

int n,l;
int a[N];
int dp[N][N][M][3];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>l;
    for(int i = 1;i <= n ; i ++) cin>>a[i];
    if(n == 1) kill(1);
    sort(a+1,a+n+1);
    a[n+1] = M*M;
    dp[0][0][0][0] = 1;
    for(int i = 1; i<= n; i ++) for(int j=1; j <= i ; j ++) for(int k = 0 ; k <= l;k ++) for(int m = 0; m < 3; m ++) {
    	int cost = (2*j-m)*(a[i+1]-a[i]);
    	if(k-cost < 0 || i + j+ 1-m > n) continue;
    	// halat aval-> componente jadid:
    	ok(dp[i][j][k][m] += dp[i-1][j-1][k-cost][m]);
    	
    	// halat dovom -> componente jadid az yeki az do sar
    	if(m)
    		ok(dp[i][j][k][m] += (3-m)*dp[i-1][j-1][k-cost][m-1]);
    	// halat sevom -> ezafe be tahe component
    	ok(dp[i][j][k][m] += (2 *j - m) * dp[i-1][j][k-cost][m]);
    	
    	// halat 4:
    	if(m == 1) {
    		ok(dp[i][j][k][m] += 2*j * dp[i-1][j][k-cost][m-1]);
    	} else if(m == 2) {
    		if(i == n) {
    			ok(dp[i][j][k][m] += dp[i-1][j][k-cost][m-1]);	
    		} else {
    			ok(dp[i][j][k][m] += (j-1)*dp[i-1][j][k-cost][m-1]);
    		}
    	}
    	// halat 5:
    	if(m == 2 && i == n) {
    		ok(dp[i][j][k][m] += dp[i-1][j+1][k-cost][m]);
    	} else if(m == 2) {
    		ok(dp[i][j][k][m] += j*(j-1)%mod*dp[i-1][j+1][k-cost][m]);
    	} else if(m == 1) {
    		ok(dp[i][j][k][m] += j*j%mod*dp[i-1][j+1][k-cost][m]);
		} else {
			ok(dp[i][j][k][m] += j*(j+1)%mod*dp[i-1][j+1][k-cost][m]);
		}
    }
    int ans =0;
    for(int i = 0 ; i <= l; i ++) ok(ans += dp[n][1][i][2]);
    cout<<ans << '\n';
	return 0;
}

// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!

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