제출 #290657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290657		Berted	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	2089 ms	22392 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, C = 10000;
using namespace std;

int n, l, ar[101], dp[2][101][C + 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[0][0][C][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			for (int k = 0; k <= C + l; k++)
			{
				for (int m = 0; m <= 2; m++)
				{
					
					dp[i & 1][j][k][m] = 0;
					if (k + 2 * ar[i - 1] <= C + l && (j > 1 || i == 1)) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(j - m) * dp[~i & 1][j - 1][k + 2 * ar[i - 1]][m]) % MD;
					}
					
					if (j < i) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(2 * j - m) * dp[~i & 1][j][k][m]) % MD; 
					}
					
					if (k - 2 * ar[i - 1] >= 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 * ar[i - 1]][m]) % MD;
					}
					
					if ((j > 1 || i == 1) && k + ar[i - 1] <= C + l && m) {dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(3 - m) * dp[~i & 1][j - 1][k + ar[i - 1]][m - 1]) % MD;}
					if (k - ar[i - 1] >= 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 - ar[i - 1]][m - 1]) % MD;}
					/*
					if (k - C >= -20 && dp[i & 1][j][k][m]) 
					{
						//if (k + 2 * ar[i - 1] <= C + l && (j > 1 || i == 1)) {cout << "New CC : " << i - 1 << " " << j - 1 << " " << k + 2 * ar[i - 1] - C << " " << m << "\n";}
						//if (j < i) cout << "Con 2CC : " << i - 1 << " " << j << " " << k - C << " " << m << "\n";
						//if (k - 2 * ar[i - 1] >= 0 && j + 1 < i && (j >= m || i == n)) {cout << "Merge CC : " << i - 1 << " " << j + 1 << " " << k - 2 * ar[i - 1] - C << " " << m << "\n";}
						//if (j && k + ar[i - 1] <= C + l && m) {cout << "Corner, newCC : " << i - 1 << " " << j - 1 << " " << k + ar[i - 1] - C << " " << m - 1 << "\n";}
						//if (k - ar[i - 1] >= 0 && m && (j >= m || i == n) && j < i) {cout << "Corner, con2oldCC : " << i - 1 << " " << j << " " << k - ar[i - 1] - C << " " << m - 1 << "\n";}
					}
					*/
				}
				
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= l; i++)
	{
		res = (res + dp[n & 1][1][C + i][2]) % MD;
	}
	cout << res << "\n";
	return 0;
}

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