제출 #332739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332739		Kevin_Zhang_TW	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	1308 ms	11500 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &v, T val) { return v < val ? (v = val, true) : false; }
template<class T>
bool chmin(T &v, T val) { return val < v ? (v = val, true) : false; }

#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_L = 1005, p = 1e9+7, MAX_N = 105, MAX_K = 3;
int n, L, a[MAX_N], cnt[MAX_N];
int dp[3][3][MAX_N][MAX_N][MAX_L], tmp[3][3][MAX_N][MAX_N][MAX_L];
void add(int &v, int val) { v += val - p, v += (v>>31) & p; }
//void add(ll &v, int val) {  return; v += val - p, v += (v>>63) & p; }
ll C(ll a, ll b) { assert(b == 2); return (a * (a-1) / 2); }
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> L;
	for (int i = 1;i <= n;++i) {
		cin >> a[i];
	}
	sort(a+1, a+n+1);

	if (n == 1) return puts("1"), 0;

	auto dp = ::dp;
	auto tmp = ::tmp;
// dp[d][a][b][c][cost]
	dp[0][0][0][0][0] = 2;
	for (int i = 0;i < n;++i) {
		int gap = a[i+1] - a[i];
		for (int d = 0;d <= 2;++d)
			for (int a = 0;a <= d;++a) 
				for (int b = 0;b <= i;++b) for (int c = 0;c + a + b <= i;++c) {
					for (int cost = 0;cost <= L;++cost) if (dp[d][a][b][c][cost]) {
						ll now = dp[d][a][b][c][cost], nc = cost + (a + (b + c) * 2) * gap;
						dp[d][a][b][c][cost] = 0;
						if (nc > L) continue;
						// if deg == 1
						if (d < 2) {
							// if point back
							// to c
							if (c) 
								add(tmp[d + 1][a + 1][b][c - 1][nc], now * 2 * c % p);
							// to b
							if (b)
								add(tmp[d + 1][a + 1][b - 1][c][nc], now * b % p);
							// to a
							if (a && b == 0 && c == 0)
								add(tmp[d + 1][a - 1][b][c][nc], now * a % p);
							// if point forward
							add(tmp[d + 1][a + 1][b][c][nc], now);
						}
						// if deg == 2
						if (a && b)
							add(tmp[d][a][b - 1][c][nc], now * a * b % p);
						if (a && c)
							add(tmp[d][a][b][c - 1][nc], now * a * c * 2 % p);
						if (b && c)
							add(tmp[d][a][b - 1][c][nc], now * b * c * 2 % p);
						// self to aa, bb, cc
						if (a >= 2)
							add(tmp[d][a - 2][b][c][nc], now);
						if (b >= 2)
							add(tmp[d][a][b - 2][c + 1][nc], now * C(b, 2) % p);
						if (c >= 2)
							add(tmp[d][a][b][c - 1][nc], now * C(c, 2) * 4 % p);
						// self be b
						add(tmp[d][a][b + 1][c][nc], now);
						// self to a, b, c
						if (a)
							add(tmp[d][a][b][c][nc], now * a % p);
						if (b)
							add(tmp[d][a][b - 1][c + 1][nc], now * b % p);
						if (c)
							add(tmp[d][a][b][c][nc], now * c * 2 % p);
					}
				}
		swap(dp, tmp);
	}
	cout << accumulate(dp[2][0][0][0], dp[2][0][0][0] + L + 1, 0ll) % p << '\n';
}

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