Submission #1204116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204116		hynmj	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	48 ms	50760 KiB

skyscraper

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define vv vector<vi>
#define vp vector<pi>
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
const int INF = 1e18, MOD = 1e9+7, MX = 102;

int a[MX], dp[MX][MX][1003][3];

void solve()
{
	int n, L; cin >> n >> L;
	if (n == 1) ret(1);

	rep(i, 1, n + 1) cin >> a[i];
	sort(a + 1, a + n + 1);
	a[n + 1] = 10000;

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

	rep(i, 1, n + 1)
	{
		rep(j, 1, i + 1)
		{
			rep(k, L + 1)
			{
				rep(m, 3)
				{
					int c = (2 * j - m) * (a[i + 1] - a[i]);
					if (k < c || i + j - m + 1 > n) continue;
					dp[i][j][k][m] += dp[i - 1][j - 1][k - c][m];
					if (m) dp[i][j][k][m] += (3 - m) * dp[i - 1][j - 1][k - c][m - 1];
					dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - c][m];
					if (m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - c][m - 1];
					if (m == 2) {
						if (i == n) dp[i][j][k][m] += dp[i - 1][j][k - c][m - 1];
						else if (j > 1) dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - c][m - 1];
						if (i == n) dp[i][j][k][m] += dp[i - 1][j + 1][k - c][m];
						else dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - c][m];
					} else if (m == 1) dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - c][m];
					else dp[i][j][k][m] += j * (j + 1) * dp[i - 1][j + 1][k - c][m];
					dp[i][j][k][m] %= MOD;
				}
			}
		}
	}

	int res = 0;
	rep(L + 1) res = (res + dp[n][1][i][2]) % MOD;
	cout << res << endl;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);  
	int ans = 1;
	rep(ans){
		solve(); ln;
	}
}

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