제출 #586594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586594		blue	Skyscraper (JOI16_skyscraper)	C++17	5 / 100	2 ms	1108 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;

const ll mod = 1'000'000'0007LL;

ll ad(ll a, ll b)
{
	return (a+b) % mod;
}

ll mul(ll a, ll b)
{
	return (a*b) % mod;
}

void selfadd(int& a, int b)
{
	a = ad(a, b);
}

int N, L;

int validlen(int x)
{
	return 0 <= x && x <= L;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> L;

	vi A(1+N, 0);
	for(int i = 1; i <= N; i++)
		cin >> A[i];

	sort(A.begin(), A.end());

	int DP[1+N][1+N][1+L][1+2];

	for(int i = 0; i <= N; i++)
		for(int j = 0; j <= N; j++)
			for(int l = 0; l <= L; l++)
				for(int e = 0; e <= 2; e++)
					DP[i][j][l][e] = 0;

	DP[1][1][0][0] = DP[1][1][0][2] = 1;
	DP[1][1][0][1] = 2;

	for(int i = 1; i <= N; i++)
	{
		// cerr << "\n\n\n";
		for(int j = 1; j <= i; j++)
		{
			// cerr << "\n\n";
			for(int l = 0; l <= L; l++)
			{
				// cerr << "\n";
				for(int e = 0; e <= 2; e++)
				{
					// cerr << i << ' ' << j << ' ' << l << ' ' << e << " : " << DP[i][j][l][e] << '\n';

					if(i >= N)
						continue;

					if(!validlen(l + (2*j - e) * (A[i+1] - A[i])))
						continue;

					// cerr << "proceeding\n";


					//case 1: building i+1 forms new component
		selfadd(DP[i+1][j+1][l + (2*j - e) * (A[i+1] - A[i])][e], mul(DP[i][j][l][e], j+1 - e));

		           //case 2: building i+1 is attached to the left/right of some component
		// if(i == 1 && j == 1 && l == 0 && e == 0)
			// cerr << DP[i][j][l][e] << ' ' << 2*j - e << " -> " << i+1 << ' ' << j << ' ' << l + (2*j - e) * (A[i+1] - A[i]) << ' ' << e << '\n';
		selfadd(DP[i+1][j][l + (2*j - e) * (A[i+1] - A[i])][e], mul(DP[i][j][l][e], 2*j - e));

				   //case 3: building i+1 merges two components
					if(j >= 2)
		selfadd(DP[i+1][j-1][l + (2*j - e) * (A[i+1] - A[i])][e], mul(DP[i][j][l][e], j-1));

				   //case 4: building i+1 creates an endpoint
					if(e < 2)
		selfadd(DP[i+1][j][l + (2*j - e) * (A[i+1] - A[i])][e+1], mul(DP[i][j][l][e], 2 - e));

					//case 5: building i+1 simultaneously forms a new component and creates endpoint
	                if(e < 2)
	    selfadd(DP[i+1][j+1][l + (2*j - e) * (A[i+1] - A[i])][e+1], mul(DP[i][j][l][e], 2 - e));
					}
			}
		}
	}

	int res = 0;

	for(int l = 0; l <= L; l++)
		res = ad(res, DP[N][1][l][2]);

	cout << res << '\n';
}

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