Submission #553368

#	Time	Username	Problem	Language	Result	Execution time	Memory
553368		sidon	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	194 ms	6640 KiB

skyscraper

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

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

int N, L, A[Z], dp[Z][1001][4], prv[Z][1001][4];

#define P(X, Y, VAL) if(_j <= L) (dp[i+X][_j][k+Y] += prv[i][j][k] * (VAL)) %= MOD;

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

	dp[1][0][0] = 1;
	dp[1][0][1] = 2;

	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 _j = j + (A[c] - A[c-1]) * (2 * i - k);
					P(1, 0, i + 1 - k);
					P(-1, 0, i - 1);
					P(0, 0, 2 * i - k);
					P(1, 1, 1 + !k);
					P(0, 1, 1 + !k);
				}
			}
		}
	}

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

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