Submission #397082

#	Time	Username	Problem	Language	Result	Execution time	Memory
397082		hltk	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	377 ms	158660 KiB

skyscraper

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define MAXN 100
#define MAXL 1001
#define MOD 1000000007

int N, L, A[MAXN];
int DP[MAXN][MAXL][2][MAXN + 1][2];

int dp(int i, int l, int kl, int k, int kr) {
	if (i == N - 1) return k == 0;

	int &ret = DP[i][l][kl][k][kr];
	if (ret != -1) return ret;

	auto get = [&](int nkl, int nk, int nkr) {
		if (nk < 0) return 0;
		int nxtl = l + (A[i + 1] - A[i]) * (nkl + nkr + nk * 2);
		return nxtl <= L ? dp(i + 1, nxtl, nkl, nk, nkr) : 0;
	};

	long long lret = 0;

	lret += 1ll * get(kl, k, kr) * k * 2 % MOD;
	lret += get(kl, k + 1, kr);
	lret += 1ll * get(kl, k - 1, kr) * k * (k - 1) % MOD;
	lret += get(1, k, kr);
	lret += get(kl, k, 1);
	lret += 1ll * get(1, k - 1, kr) * k % MOD;
	lret += 1ll * get(kl, k - 1, 1) * k % MOD;

	return ret = (int) (lret % MOD);
}

int main() {
	scanf("%d %d", &N, &L);

	for (int i = 0; i < N; ++i)
		scanf("%d", A + i);

	sort(A, A + N);

	memset(DP, -1, sizeof(DP));

	printf("%d\n", dp(0, 0, 0, 0, 0));
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d %d", &N, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

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