제출 #26104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26104		gabrielsimoes	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	39 ms	246516 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 102;
const int MAXL = 1002;
const ll MOD = 1e9+7;

#define upd(x, a) ((x) = ((x) + (a)) % MOD)

int N, L;
vector<int> v;
ll dp[MAXN][MAXN][3][MAXL];

int main()
{
	ios_base::sync_with_stdio(0);
	cin >> N >> L;

	v.resize(N);
	for (int i = 0; i < N; i++) cin >> v[i];
	sort(v.begin(), v.end());

	if (N == 1) return cout << 1 << endl, 0;

	v.push_back(MAXL*100);
	if (v[1] - v[0] <= L) dp[1][1][1][v[1]-v[0]] = 2;
	if (2*(v[1] - v[0]) <= L) dp[1][1][0][2*(v[1]-v[0])] = 1;

	int nsum; ll cur;
	for (int i = 1; i <= N; i++) {
		int dif = v[i+1] - v[i];
		for (int cnt = 1; cnt <= i; cnt++) {
			for (int end = 0; end < 3; end++) {
				for (int sum = 0; sum <= L; sum++) {
					cur = dp[i][cnt][end][sum];
					if (cur == 0) continue;

					// try to fill the ends
					nsum = sum + dif*(2*cnt - end - 1);
					if (end < 2 && nsum <= L) {
						// no new component is created
						if (i == N-1) upd(dp[i+1][cnt][end+1][nsum], cur);
						else if (end == 0 || cnt > 1) upd(dp[i+1][cnt][end+1][nsum], ll(2-end)*ll(cnt-end)*cur);

						// a new component is created
						nsum += 2*dif;
						if (nsum <= L) upd(dp[i+1][cnt+1][end+1][nsum], ll(2-end)*cur);
					}

					// try to create a new component
					nsum = sum + dif*(2*cnt - end) + 2*dif;
					if (nsum <= L) upd(dp[i+1][cnt+1][end][nsum], cur);

					// try append to a component
					nsum = sum + dif*(2*cnt - end);
					if (nsum <= L) upd(dp[i+1][cnt][end][nsum], ll(2*cnt-end)*cur);

					// join two components together
					nsum = sum + dif*(2*cnt - end) - 2*dif;
					if (nsum <= L && cnt >= 2 && (i == N-1 || cnt > 2 || end < 2)) {
						if (end == 0) upd(dp[i+1][cnt-1][end][nsum], ll(cnt)*ll(cnt-1)*cur);
						else if (end == 1) upd(dp[i+1][cnt-1][end][nsum], ll(cnt-1)*ll(cnt-1)*cur);
						else if (end == 2) {
							if (i == N-1) upd(dp[i+1][cnt-1][end][nsum], cur);
							else upd(dp[i+1][cnt-1][end][nsum], ll(cnt-2)*ll(cnt-1)*cur);
						}
					}
				}
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i <= L; i++)
		upd(ans, dp[N][1][2][i]);
	cout << ans << endl;
}

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