Submission #397081

#	Time	Username	Problem	Language	Result	Execution time	Memory
397081		hltk	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	390 ms	158652 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;

	// kl = 1 if there is a segment connected to the left border, 0 otherwise
	// kr = 1 if there is a segment connected to the right border, 0 otherwise
	// k is the number of segments in the middle

	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 += get(kl, k, kr) * k * 2;           // extend some middle segment
	lret += get(kl, k + 1, kr);               // create a new middle segment
	lret += get(kl, k - 1, kr) * k * (k - 1); // join two middle segments
	lret += get(1, k, kr);                    // place current element at the left border
	lret += get(kl, k, 1);                    // place current element at the right border
	lret += get(1, k - 1, kr) * k;            // place current element at the left border and join it to a preexisting segment
	lret += get(kl, k - 1, 1) * k;            // place current element at the right border and join it to a preexisting segment

	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:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d %d", &N, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

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