Submission #362802

#	Time	Username	Problem	Language	Result	Execution time	Memory
362802		QCFium	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	321 ms	3564 KiB

skyscraper

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

#define MOD 1000000007

int main() {
	int n = ri();
	
	// !!!! corner case n <= 2  !!!!
	
	int l = ri();
	int a[n];
	for (auto &i : a) i = ri();
	
	std::sort(a, a + n);
	
	int dp[l + 1][n][2][2];
	memset(dp, 0, sizeof(dp));
	
	auto add = [&] (int &a, int b) {
		a += b;
		if (a >= MOD) a -= MOD;
	};
	
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) dp[0][0][i][j] = 1;
	for (int i = 1; i < n; i++) {
		int len = a[i] - a[i - 1];
		
		int tmp[l + 1][n][2][2];
		memset(tmp, 0, sizeof(tmp));
		for (int j = 0; j <= l; j++) for (int k = 0; k < n; k++)
			for (int p = 0; p < 2; p++) for (int q = 0; q < 2; q++)
				if (j + (k + p + q) * len <= l && (k + k + p + q)) add(tmp[j + (k + k + p + q) * len][k][p][q], dp[j][k][p][q]);
		memset(dp, 0, sizeof(dp));
		
		for (int j = 0; j <= l; j++) {
			for (int k = 0; k < n; k++) {
				for (int p = 0; p < 2; p++) {
					for (int q = 0; q < 2; q++) {
						if (!tmp[j][k][p][q]) continue;
						// fprintf(stderr, "at %d, used : %d, (%d, %d, %d) : %d\n", i, j, p, k, q, tmp[j][k][p][q]);
						if (p) {
							add(dp[j][k][0][q], tmp[j][k][p][q]);
							add(dp[j][k][p][q], tmp[j][k][p][q]);
							add(dp[j][k + 1][0][q], tmp[j][k][p][q]);
							add(dp[j][k + 1][p][q], tmp[j][k][p][q]);
						}
						if (q) {
							add(dp[j][k][p][0], tmp[j][k][p][q]);
							add(dp[j][k][p][q], tmp[j][k][p][q]);
							add(dp[j][k + 1][p][0], tmp[j][k][p][q]);
							add(dp[j][k + 1][p][q], tmp[j][k][p][q]);
						}
						if (k) {
							add(dp[j][k - 1][p][q], (int64_t) tmp[j][k][p][q] * k % MOD);
							add(dp[j][k][p][q], (int64_t) tmp[j][k][p][q] * k % MOD);
							add(dp[j][k][p][q], (int64_t) tmp[j][k][p][q] * k % MOD);
							add(dp[j][k + 1][p][q], (int64_t) tmp[j][k][p][q] * k % MOD);
						}
					}
				}
			}
		}
	}
	
	int res = 0;
	for (int i = 0; i <= l; i++) add(res, dp[i][0][0][0]);
	printf("%d\n", res);
	
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int ri()':
skyscraper.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    5 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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