Submission #1193917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193917		AMnu	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	103 ms	151352 KiB

skyscraper

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

const ll MOD = 1e9+7, MAXN = 1e2+5, MAXL = 1e3+5;

int N, L, A[MAXN], cost;
ll dp[MAXN][MAXN][4][MAXL], sum;

int main () {
	cin >> N >> L;
	for (int i=1;i<=N;i++) {
		cin >> A[i];
	}
	sort(A+1,A+N+1);
	dp[1][1][0][0] = 1;
	dp[1][1][1][0] = 2;
	dp[1][1][2][0] = 1;
	for (int i=1;i<N;i++) {
		for (int j=1;j<=i;j++) {
			for (int k=0;k<3;k++) {
				cost = (A[i+1]-A[i])*(2*j-k);
				for (int l=cost;l<=L;l++) {
					dp[i+1][j-1][k][l] += dp[i][j][k][l-cost]*(j-1);
					dp[i+1][j][k][l] += dp[i][j][k][l-cost]*(2*j-k);
					dp[i+1][j][k+1][l] += dp[i][j][k][l-cost]*(2-k);
					dp[i+1][j+1][k][l] += dp[i][j][k][l-cost]*(j+1-k);
					dp[i+1][j+1][k+1][l] += dp[i][j][k][l-cost]*(2-k);
					dp[i+1][j-1][k][l] %= MOD;
					dp[i+1][j][k][l] %= MOD;
					dp[i+1][j][k+1][l] %= MOD;
					dp[i+1][j+1][k][l] %= MOD;
					dp[i+1][j+1][k+1][l] %= MOD;
				}
			}
		}
	}
	for (int i=0;i<=L;i++) {
		sum += dp[N][1][2][i];
		sum %= MOD;
	}
	cout << sum << "\n";
}

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