Submission #159953

#	Time	Username	Problem	Language	Result	Execution time	Memory
159953		iefnah06	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	61 ms	3192 KiB

skyscraper

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

typedef unsigned int uint;
typedef unsigned long long ull;

const uint MOD = 1e9 + 7;

struct num {
	uint v;
	num(uint _v = 0) : v(_v) { }

	num& operator += (const num& r) {
		if ((v += r.v) >= MOD) v -= MOD;
		return *this;
	}
	num& operator *= (const num& r) {
		v = (ull)v * r.v % MOD;
		return *this;
	}

	num operator + (const num& r) const { return num(*this) += r; }
	num operator * (const num& r) const { return num(*this) *= r; }
};

const int MAXN = 110;
const int MAXL = 1010;
int N;
int L;

int A[MAXN];

num dp[MAXN][MAXL][3];
num ndp[MAXN][MAXL][3];

void append(int deltaA) {
	memset(ndp, 0, sizeof(ndp));
	for (int c = 0; c <= N; c++) {
		for (int v = 0; v <= L; v++) {
			for (int t = 0; t <= 2; t++) {
				int nv = v + deltaA * (t + 2 * c);
				if (nv > L || !dp[c][v][t].v) continue;

				// head or tail
				if (t) {
					num ways = dp[c][v][t] * t;
					ndp[c+1][nv][t] += ways;
					ndp[c+1][nv][t-1] += ways;
					ndp[c][nv][t] += ways;
					ndp[c][nv][t-1] += ways;
				}

				// some gap in the middle
				if (c) {
					num ways = dp[c][v][t] * c;
					ndp[c+1][nv][t] += ways;
					ndp[c][nv][t] += ways * 2;
					ndp[c-1][nv][t] += ways;
				}
			}
		}
	}
	memcpy(dp, ndp, sizeof(ndp));
}

int main() {
	scanf("%d %d", &N, &L);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}

	sort(A, A + N);
	dp[0][0][0] = 1;
	dp[0][0][1] = 2;
	dp[0][0][2] = 1;
	for (int i = 1; i < N; i++) {
		append(A[i] - A[i-1]);
	}

	num ans = 0;
	for (int v = 0; v <= L; v++) {
		ans += dp[0][v][0];
	}
	printf("%u\n", ans.v);

	return 0;
}

Compilation message (stderr)

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

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