oj.uz

Submission #1043349

# Submission time Handle Problem Language Result Execution time Memory
1043349 2024-08-04T08:41:06 Z Aldas25 Skyscraper (JOI16_skyscraper) C++14
15 / 100
 1 ms 860 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;
const int MAXN = 110;
const int MAXL = 1010;

int n, l;
int a[MAXN];
ll dp[MAXN][MAXN][MAXL][3];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);

	cin >> n >> l;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1);

	dp[0][0][0][0] = 1;
	a[n+1] = MAXL;

	for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) for (int m = 0; m <= 2; m++) {
		ll delta = (a[i+1] - a[i]) * ((ll)(2 * j - m));
		
		for (int k = delta; k <= l; k++) {
			int prevK = k - delta;
			ll val = 0;
			// Case 1
			val += dp[i-1][j-1][prevK][m];
			
			// Case 2
			if (m > 0) 
				val += ((ll)(3 - m)) * dp[i-1][j-1][prevK][m-1];

			// Case 3
			val += ((ll)(2 * j - m)) * dp[i-1][j][prevK][m];
			
			// Case 4
			if (m == 1) {
				val += ((ll)(2 * j)) * dp[i-1][j][prevK][m-1];
			} else if (m == 2 && j == 1 && i == n)
				val += dp[i-1][j][prevK][m-1];
			else if (m == 2 && j != 1)
				val += ((ll)(j-1)) * dp[i-1][j][prevK][m-1];

			// Case 5
			if (i == n && j == 1 && m == 2)
				val += dp[i-1][j+1][prevK][m];
			else if (i != n) {
				ll mult = 0;
				if (m == 0) mult = (j + 1) * j;
				else if (m == 1) mult = j * j;
				else mult = (j - 1) * j;

				val += mult * dp[i-1][j+1][prevK][m];
			}

			dp[i][j][k][m] = val % MOD;
		}
	}

	ll ans = 0;
	for (int k = 0; k <= l; k++) ans = (ans + dp[n][1][k][2]) % MOD;

	cout << (ans % MOD) << "\n";

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -