Submission #290682

#	Time	Username	Problem	Language	Result	Execution time	Memory
290682		Berted	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	165 ms	2936 KiB

skyscraper

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <iostream>
#include <algorithm>
#define ll long long
const int MD = 1e9 + 7;
using namespace std;

int n, l, ar[101], dp[2][101][1001][3];

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> l;
	if (n == 1) {cout << "1\n"; return 0;}
	for (int i = 0; i < n; i++) {cin >> ar[i];}
	sort(ar, ar + n);
	dp[1][1][0][0] = 1;
	dp[1][1][0][1] = 2;
	for (int i = 2; i <= n; i++)
	{
		for (int k = 0; k <= l; k++)
		{
			for (int m = 0; m <= 2; m++) {dp[i & 1][0][k][m] = 0;}
		}
		for (int j = 1; j <= i; j++)
		{
			for (int k = 0; k <= l; k++)
			{
				for (int m = 0; m <= 2; m++)
				{
					int v = ar[i - 1] - ar[i - 2]; dp[i & 1][j][k][m] = 0;
					if (k - (2 * j - 2 - m) * v >= 0) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(j - m) * dp[~i & 1][j - 1][k - (2 * j - 2 - m) * v][m]) % MD;
					}
					
					if (k - (2 * j - m) * v >= 0) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(2 * j - m) * dp[~i & 1][j][k - (2 * j - m) * v][m]) % MD; 
					}
					
					if (k - (2 * j + 2 - m) * v >= 0 && j + 1 < i && (j >= m || i == n)) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)j * dp[~i & 1][j + 1][k - (2 * j + 2 - m) * v][m]) % MD;
					}
					
					if (k - (2 * j - m - 1) * v>= 0 && m) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(3 - m) * dp[~i & 1][j - 1][k - (2 * j - m - 1) * v][m - 1]) % MD;
					}
					if (k - (2 * j - m + 1)  * v>= 0 && m && (j >= m || i == n) && j < i) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(3 - m) * dp[~i & 1][j][k - (2 * j - m + 1) * v][m - 1]) % MD;
					}
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= l; i++)
	{
		res = (res + dp[n & 1][1][i][2]) % MD;
	}
	cout << res << "\n";
	return 0;
}

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