제출 #586603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586603		blue	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	166 ms	89096 KiB

skyscraper

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

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

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

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

int main()
{
	int N, L;
	cin >> N >> L;

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

	int DP[(1<<N)][N][1+L];
	for(int m = 0; m < (1<<N); m++)
		for(int i = 0; i < N; i++)
			for(int l = 0; l <= L; l++)
				DP[m][i][l] = 0;

	for(int i = 0; i < N; i++)
		DP[(1<<i)][i][0] = 1;

	for(int m = 0; m < (1<<N); m++)
	{
		for(int i = 0; i < N; i++)
		{
			if(!(m & (1<<i)))
				continue;

			if(m == (1<<i))
				continue;

			int m2 = m ^ (1<<i);

			for(int j = 0; j < N; j++)
			{
				if(!(m2 & (1<<j)))
					continue;

				for(int l = abs(A[i] - A[j]); l <= L; l++)
					DP[m][i][l] = ad(DP[m][i][l], DP[m2][j][l - abs(A[i] - A[j])]);
			}
		}
	}

	int res = 0;
	for(int i = 0; i < N; i++)
		for(int z = 0; z <= L; z++)
			res = ad(res, DP[(1<<N) - 1][i][z]);

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

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