Submission #553360

#	Time	Username	Problem	Language	Result	Execution time	Memory
553360		sidon	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	196 ms	5072 KiB

skyscraper

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

const int MOD = 1e9+7, Z = 1e2 + 1, LIM = 1e3 + 1;

int N, L, A[Z], dp[Z][LIM][3], prv[Z][LIM][3];

#define push(X, Y, Z, VAL) (dp[X][Y][Z] += VAL) %= MOD;

int32_t main() {
	cin >> N >> L;
	for(int i = 0; i < N; ++i)
		cin >> A[i];
	sort(A, A + N);

	dp[1][0][0] = 1;
	dp[1][0][1] = 2;
	if(N < 2)
		dp[1][0][2] = 1;

	for(int c = 1; c < N; ++c) {
		swap(prv, dp);
		memset(dp, 0, sizeof dp);

		for(int i = 1; i < N; ++i) {
			for(int j = 0; j < L; ++j) {
				for(int k = 0; k < 3; ++k) {
					int diff = j + (A[c] - A[c-1]) * (2 * i - k);
					if(diff >= LIM) continue;

					push(i + 1, diff, k, prv[i][j][k] * (i + 1 - k));
					push(i - 1, diff, k, prv[i][j][k] * (i - 1));
					push(i + 0, diff, k, prv[i][j][k] * (2 * i - k));

					if(k < 2) {
						push(i + 1, diff, k + 1, prv[i][j][k] * (1 + !k));
						push(i + 0, diff, k + 1, prv[i][j][k] * (1 + !k));
					}
				}
			}
		}
	}

	int ans {};
	for(int i = 0; i <= L; ++i)
		(ans += dp[1][i][2]) %= MOD;
	cout << ans;
}

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